Ransom Note, thesarfo

Given ransomNote and magazine, return true if ransomNote can be built using letters from magazine (each letter usable once). ransomNote = "aa", magazine = "aab" → true; ransomNote = "aa", magazine = "ab" → false. (LeetCode 383)

Approach — hash table / array: use an array cnt of length 26 to count how many times each character appears in magazine. Traverse ransomNote, decrementing cnt[c] for each character. If any count drops below 0, magazine doesn’t have enough of that character, so return false. If the traversal completes, every character in ransomNote was available in magazine, so return true.

Time: O(m + n). Space: O(C), where C is 26 (the alphabet size).

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        cnt = Counter(magazine)
        for c in ransomNote:
            cnt[c] -= 1
            if cnt[c] < 0:
                return False
        return True

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] cnt = new int[26];
        for (int i = 0; i < magazine.length(); ++i) {
            ++cnt[magazine.charAt(i) - 'a'];
        }
        for (int i = 0; i < ransomNote.length(); ++i) {
            if (--cnt[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}