Ransom Note
Asked at Anduril
Problem
Ransom Note asks whether you can build the string ransomNote using letters cut out of magazine, where each magazine letter can be used only once. It is a quick counting question that checks you reach for a frequency table instead of searching the magazine repeatedly.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Easy | View all Anduril questions → |
How to Think About It
Brute force: for each letter in the note, search the magazine and remove the first match. That is O(n * m).
Key insight: only letter counts matter, not positions. Count each letter in the magazine, then spend those counts on the note.
Use a 26-length array since the inputs are lowercase letters. Increment for magazine letters; decrement for note letters and fail as soon as a count goes negative.
Walkthrough: note "aa", magazine "aab": counts a=2, b=1. Spend a twice -> a=0. Never negative -> true. Note "aa", magazine "ab" -> second a drives the count to -1 -> false.
Quick exit: if the note is longer than the magazine, the answer is false.
Optimal Approach
Step 1: If len(ransomNote) > len(magazine), return false.
Step 2: count = [0] * 26; for each char in magazine, increment its count.
Step 3: For each char in ransomNote: decrement its count; if it becomes negative, return false.
Step 4: Return true.
Time: O(n + m). Space: O(1) (26 counters).
What Trips People Up in Real Interviews
Checking membership only (ch in magazine). That ignores multiplicity — the note "aa" cannot be built from the magazine "a".
Mutating strings with replace to remove used letters. It works but is quadratic and allocates new strings every time.
Counting the note and the magazine separately and then comparing — fine, but the single table with early exit is simpler.
Not asking about the character set. If Unicode is possible, switch the array to a hash map.
Solution Code
def canConstruct(ransomNote, magazine):
if len(ransomNote) > len(magazine):
return False
count = [0] * 26
for ch in magazine:
count[ord(ch) - ord('a')] += 1
for ch in ransomNote:
i = ord(ch) - ord('a')
count[i] -= 1
if count[i] < 0:
return False
return TrueFrequently Asked Questions
What is the Ransom Note problem?
Ransom Note asks whether you can build the string `ransomNote` using letters cut out of `magazine`, where each magazine letter can be used only once. It is a quick counting question that checks you reach for a frequency table instead of searching the magazine repeatedly.
How do you solve Ransom Note?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Ransom Note?
Ransom Note is asked at Anduril. It is a easy difficulty problem.
What are common mistakes on Ransom Note?
- Checking membership only (`ch in magazine`). That ignores multiplicity — the note `"aa"` cannot be built from the magazine `"a"`.
- Mutating strings with `replace` to remove used letters. It works but is quadratic and allocates new strings every time.
- Counting the note and the magazine separately and then comparing — fine, but the single table with early exit is simpler.
- Not asking about the character set. If Unicode is possible, switch the array to a hash map.