1. Brute Force

Intuition

For each character in the ransom note, we search for a matching character in the magazine. When found, we remove that character from the magazine so it cannot be reused. If any character cannot be found, we know the ransom note cannot be constructed.

Algorithm

1. Convert the magazine string to a mutable list of characters.
2. For each character c in the ransom note:
   • If c is not in the magazine list, return false.
   • Otherwise, remove one occurrence of c from the magazine list.
3. If all characters are found, return true.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine = list(magazine)

        for c in ransomNote:
            if c not in magazine:
                return False
            else:
                magazine.remove(c)
        
        return True

Time & Space Complexity

• Time complexity: $O(m * n)$
• Space complexity: $O(n)$

Where $m$ and $n$ are the lengths of the strings $ransomNote$ and $magazine$, respectively.

---

2. Count Frequency

Intuition

Instead of searching and removing characters one by one, we can count the frequency of each character in both strings. The ransom note can be constructed if and only if the magazine contains at least as many of each character as the ransom note requires.

Algorithm

1. Count the frequency of each character in the ransom note (countR).
2. Count the frequency of each character in the magazine (countM).
3. For each character in countR:
   • If countM[c] < countR[c], return false.
4. Return true.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        countR = Counter(ransomNote)
        countM = Counter(magazine)

        for c in countR:
            if countM[c] < countR[c]:
                return False

        return True

Time & Space Complexity

• Time complexity: $O(m + n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $m$ and $n$ are the lengths of the strings $ransomNote$ and $magazine$, respectively.

---

3. Count Frequency (Optimal)

Intuition

We can optimize further by using a single count array. First, we count all characters in the magazine. Then, as we iterate through the ransom note, we decrement the count for each character. If any count goes negative, the magazine does not have enough of that character.

Algorithm

1. Create a count array of size 26 (for lowercase letters).
2. For each character in the magazine, increment its count.
3. For each character in the ransom note:
   • Decrement its count.
   • If the count becomes negative, return false.
4. Return true.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26
        for c in magazine:
            count[ord(c) - ord('a')] += 1

        for c in ransomNote:
            count[ord(c) - ord('a')] -= 1
            if count[ord(c) - ord('a')] < 0:
                return False

        return True

Time & Space Complexity

• Time complexity: $O(m + n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $m$ and $n$ are the lengths of the strings $ransomNote$ and $magazine$, respectively.

---

Common Pitfalls

Counting the Wrong String First

A common mistake is counting characters from the ransom note first and then trying to match against the magazine. This leads to incorrect logic when checking availability. Always count the magazine characters first (the source), then verify against the ransom note requirements.

Not Handling Character Reuse Properly

When using the brute force approach, forgetting to remove a character from the magazine after using it leads to incorrect results. Each magazine character can only be used once, so after matching a character, it must be marked as consumed to prevent reuse.