Ransom Note
Ransom Note: decide whether ransomNote can be built from the letters in magazine, where each letter in the magazine may be used at most once.
- 1 <= ransomNote.length, magazine.length <= 10⁵
- ransomNote and magazine consist of lowercase English letters
Intuition
Order is irrelevant — only how many of each letter you have. So reduce both strings to letter counts and ask whether the magazine's supply covers the note's demand for every letter. Counting the magazine once and then spending from that stock as the note is read turns the question into a single pass over each string, with no need to search the magazine repeatedly.
Whenever a problem asks whether one collection can be assembled from another and order does not matter, it is a counting question. The tell is repeated letters mattering. Valid Anagram is the symmetric version, requiring equality of counts rather than containment.
Approach
Before reading on: work out why checking that every letter of the note merely appears in the magazine is not enough. Construct the smallest pair of strings where that check passes but the answer should be false.
Multiset containment, not substring matching
The note is constructible exactly when, for every letter, the magazine holds at least as many copies as the note requires. That is a multiset containment test. Position plays no part: abc and cba are equally buildable from the same magazine. Recognising this rules out the whole family of scanning and matching approaches and replaces them with counting, which is why the solution is linear rather than quadratic.
Count the supply, then spend it
Build a frequency map of magazine in one pass. Then walk ransomNote and, for each character, decrement its count. If a count is already zero or the letter is missing entirely, the demand exceeds the supply and the answer is false immediately. Decrementing is what enforces the each letter used once rule — without it, a magazine containing a single a would wrongly satisfy a note needing three, because a membership test alone cannot tell one copy from many.
Cost, and the early exit
Counting the magazine is O(m); scanning the note is O(n), so the total is O(m + n) — strictly better than the O(n · m) of searching the magazine for each character. Space is O(k) where k is the alphabet size, bounded at 26 for lowercase English letters, which makes it effectively O(1). A useful shortcut: if len(ransomNote) > len(magazine) the answer is false before any counting, since the note cannot need fewer letters than it has characters.
Solution & live demo
Common pitfalls
Testing membership instead of counts
for ch in ransomNote:
if ch not in magazine:
return Falseif stock[ch] == 0:
return False
stock[ch] -= 1Membership cannot distinguish one copy from many. Note 'aa' with magazine 'ab' passes this check but is not buildable, because the single 'a' would have to be used twice.
Forgetting to decrement after use
if stock[ch] == 0:
return Falseif stock[ch] == 0:
return False
stock[ch] -= 1Without spending the letter, the same copy satisfies every occurrence in the note, so any note made of one repeated character passes as long as the magazine holds one of it.
Counting the note instead of the magazine
need = Counter(ransomNote)
for ch in magazine:
need[ch] -= 1stock = Counter(magazine)
for ch in ransomNote:
...This direction cannot exit early on failure and must scan the entire magazine before checking whether any count remains positive, doing more work and complicating the final test.
Edge cases
Impossible by pigeonhole; the length check rejects it immediately.
Nothing is required, so the answer is true for any magazine.
The second 'a' finds a count of zero and fails, which a membership test would miss.
Leftovers are simply never spent and do not affect the result.
Every count lands at zero and the note is buildable.