Ransom Note

How it works

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.

Steps

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.

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.

Things to watch for

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.

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

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int count[26] = {};
        for (char c : magazine) {
            count[c - 'a']++;
        }
        for (char c : ransomNote) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }
};