Ransom Note
Can `ransomNote` be built from `magazine`'s letters? Letter-count subset check.
2 min read
hash-map counting strings
Problem#
Given ransomNote and magazine, return true iff every letter in ransomNote is available in magazine with at least its required multiplicity (each magazine letter usable once).
Examples#
ransomNote = "a", magazine = "b"→false.ransomNote = "aa", magazine = "aab"→true.
Constraints#
1 <= ransomNote.length, magazine.length <= 10^5, lowercase.
Hints#
Hint
Counter from magazine; decrement on each ransom letter, fail if it goes negative.
Approach#
Count magazine letters. For each character in ransomNote, decrement; if any drops below zero, return false.
Solution#
class Solution {public: bool canConstruct(string ransomNote, string magazine) { int cnt[26] = {0}; for (char c : magazine) ++cnt[c - 'a']; for (char c : ransomNote) { if (--cnt[c - 'a'] < 0) return false; } return true; }};func canConstruct(ransomNote string, magazine string) bool { var cnt [26]int for i := 0; i < len(magazine); i++ { cnt[magazine[i]-'a']++ } for i := 0; i < len(ransomNote); i++ { cnt[ransomNote[i]-'a']-- if cnt[ransomNote[i]-'a'] < 0 { return false } } return true}from collections import Counter
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 Truefunction canConstruct(ransomNote, magazine) { const cnt = new Array(26).fill(0); const A = 'a'.charCodeAt(0); for (let i = 0; i < magazine.length; i++) cnt[magazine.charCodeAt(i) - A]++; for (let i = 0; i < ransomNote.length; i++) { if (--cnt[ransomNote.charCodeAt(i) - A] < 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; }}function canConstruct(ransomNote: string, magazine: string): boolean { const cnt: number[] = new Array<number>(26).fill(0); const A = 'a'.charCodeAt(0); for (let i = 0; i < magazine.length; i++) cnt[magazine.charCodeAt(i) - A]++; for (let i = 0; i < ransomNote.length; i++) { if (--cnt[ransomNote.charCodeAt(i) - A] < 0) return false; } return true;}Editorial#
Magazine letters are consumable: each one in the counter supports exactly one ransom letter. Failure is purely a negative-count check, so the loop bails the moment we run out.
Complexity#
- Time: O(N + M).
- Space: O(1).
Concept revision#
Related#