Ransom Note
Ransom Note is LeetCode 383 (Easy). You get two strings, ransomNote and magazine. Return true if the note can be assembled from letters cut out of the magazine, and false otherwise.
- Each letter in
magazinecan be used at most once. Two copies of a letter in the note need two copies in the magazine. - Order does not matter: the letters can be taken from anywhere in the magazine.
- The magazine may contain extra letters the note never uses.
- Both strings contain only lowercase English letters, and each is up to 10⁵ characters long, so the check should be linear, and a fixed table of 26 counts is enough.
- 1 <= ransomNote.length, magazine.length <= 10⁵
- ransomNote and magazine consist of lowercase English letters
Intuition
This question is about quantities, not presence. Picture each magazine letter as a physical cut-out: once it is glued into the note it is gone, so the magazine is a stock of copies per letter, and the note spends that stock.
The note is buildable exactly when no letter is spent more often than it is stocked. Keeping one count per letter, adding for the magazine and subtracting for the note, checks that for all letters at once in a single pass over each string.
"Can collection A be assembled from collection B, using each item of B once, in any order?" is a multiset-containment question: count B, then subtract A and watch for a count going below zero. Valid Anagram (242) is the stricter sibling, where the counts must match exactly rather than merely cover.
Approach
Before reading on, find the shortest note and magazine where "every note letter appears somewhere in the magazine" is true but the answer is still false. Then aim for O(m + n) time with constant extra space.
Reject a note that is too long
Return false at once when len(ransomNote) > len(magazine). Each note letter consumes one magazine letter, so a longer note can never fit, and this O(1) check skips both loops on hopeless inputs.
Count the magazine
Make stock = [0] * 26 and add 1 at ord(ch) - ord('a') for every magazine letter. A plain array works because the input is only lowercase letters, and after this pass stock[k] is the number of copies of letter k you can cut out.
Spend letters for the note
Walk the note and, for each letter:
stock[k] == 0– no copy is left, so returnfalseimmediately.- otherwise – decrement
stock[k]; that copy is glued in and cannot be reused.
If the loop finishes, every letter found a copy, so return true.
Why counting letters is enough
After each note letter, stock[k] equals magazine copies minus note copies seen so far. It is 0 at the moment of use only when the note asks for more of that letter than the magazine holds, so the loop fails on exactly the impossible notes.
Ransom Note solution in Python | C++ | Java
ch in magazine test would wrongly say yes here.Common pitfalls
Checking membership instead of counts
for ch in ransomNote:
if ch not in magazine:
return False
return Trueif stock[k] == 0:
return False
stock[k] -= 1"aa" against "ab" passes the membership test twice using the same single a. It is also O(m·n), because in on a string is a linear scan.
Checking the count but never decrementing
if stock[k] == 0:
return Falseif stock[k] == 0:
return False
stock[k] -= 1Without the decrement the count never falls, so one copy satisfies every repeat of that letter. This is the membership bug again in a different form.
Removing characters from the magazine string
for ch in ransomNote:
if ch not in magazine:
return False
magazine = magazine.replace(ch, "", 1)stock = [0] * 26
for ch in magazine:
stock[ord(ch) - ord("a")] += 1It gives the right answer, but each replace copies the whole string, so the run is O(m·n). With 10⁵ characters on each side that is far too slow; counting is O(m + n).
Complexity
LeetCode 383 vs the HackerRank ransom note
HackerRank's version ("Hash Tables: Ransom Note") has the same story, but it counts whole words, which changes the data structure.
| LeetCode 383 | HackerRank | |
|---|---|---|
| Unit | single lowercase letters | space-separated words, case-sensitive |
| Counter | array of 26 ints | hash map from word to count |
| Output | return true / false | print Yes / No |
| Idea | count supply, spend demand | same: count supply, spend demand |
Ransom Note FAQ
What is the shortest Python solution?
return not Counter(ransomNote) - Counter(magazine). Subtracting Counters drops counts that fall to zero or below, so anything left is a letter the note needs more of than the magazine has. It is O(m + n) too, but always scans both strings fully, while the counting loop can stop at the first shortage.
Why use an array of 26 instead of a dictionary?
The input is limited to lowercase English letters, so ord(ch) - ord('a') is a perfect index from 0 to 25. An array avoids hashing and gives the same O(1) space. If the input could be any Unicode text, a dictionary would be the right choice.
Can you count the note and walk the magazine instead?
Yes: count what the note needs, decrement as matching magazine letters arrive, and return true once every need is met. That can stop early when the note is covered, but it has no early exit for failure, so an impossible note always costs a full magazine scan.