Ransom Note
Decide whether one string can be built from the letters of another, using each letter at most once. A short exercise in counting characters with a hash map or a fixed-size array. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given two strings, ransomNote and magazine. Return true if you can spell ransomNote by cutting letters out of magazine, and false otherwise.
Each letter in magazine can be used at most once. The order of letters doesn't matter, only how many of each you have.
Example 1
- Input
- ransomNote = "tea", magazine = "great"
- Output
- true
"great" has a t, an e, and an a to spare.
Example 2
- Input
- ransomNote = "tattoo", magazine = "toast"
- Output
- false
The note needs three t letters but "toast" only has two.
Example 3
- Input
- ransomNote = "zz", magazine = "zaz"
- Output
- true
Constraints
- 1 ≤ ransomNote.length, magazine.length ≤ 10⁵
- Both strings contain only lowercase English letters.
- Each magazine letter can be used once.
Practice
Runs 14 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Ransom Note in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Ransom Note
Pattern: Character frequency counting
Since order doesn't matter, each string is really just a bag of letters. The note can be built exactly when, for every letter, the magazine has at least as many copies as the note needs.
Count the magazine's letters once. Then walk the note and spend one copy per letter. If a count would go below zero, you've run out of that letter and the answer is false. With only 26 lowercase letters, a fixed array of 26 counters is enough and is faster than a general hash map.
Approach 1: Remove letters one at a time
For each letter of the note, search the magazine for an unused copy and remove it (or mark it used). Correct, but each search can scan the whole magazine.
Time O(m · n) · Space O(n) for a mutable copy of the magazine
Approach 2: Sort both and merge
Sort both strings, then walk them with two pointers, matching each note letter against the next equal magazine letter and skipping extra magazine letters. Works, but sorting is more than you need.
Time O(m log m + n log n) · Space O(m + n)
Approach 3: Count the magazine, spend on the note
- If the note is longer than the magazine, return
falseright away. - Build a 26-slot count of the magazine's letters.
- For each letter in the note, decrement its count. If it drops below 0, return
false. - Return
true.
Each character is touched once and the counter array has a fixed size.
Time O(m + n) · Space O(1) (26 counters)
| Approach | Time | Space |
|---|---|---|
| Remove letters one at a time | O(m · n) | O(n) for a mutable copy of the magazine |
| Sort both and merge | O(m log m + n log n) | O(m + n) |
| Count the magazine, spend on the note | O(m + n) | O(1) (26 counters) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Ransom Note solution in Python
def can_construct(ransom_note: str, magazine: str) -> bool:
if len(ransom_note) > len(magazine):
return False
counts = [0] * 26
for ch in magazine:
counts[ord(ch) - 97] += 1
for ch in ransom_note:
i = ord(ch) - 97
counts[i] -= 1
if counts[i] < 0:
return False
return TrueRansom Note solution in JavaScript
function canConstruct(ransomNote, magazine) {
if (ransomNote.length > magazine.length) return false;
const counts = new Array(26).fill(0);
for (let i = 0; i < magazine.length; i++) counts[magazine.charCodeAt(i) - 97]++;
for (let i = 0; i < ransomNote.length; i++) {
const c = ransomNote.charCodeAt(i) - 97;
if (--counts[c] < 0) return false;
}
return true;
}Common mistakes
- Checking only whether each note letter appears in the magazine, ignoring how many times it is needed ("tattoo" from "toast").
- Counting the note and the magazine but comparing in the wrong direction, so a magazine with fewer letters passes.
- Removing characters from a string inside a loop, which is quadratic because each removal copies the string.
- Swapping the arguments. The first string is the note, the second is the source of letters.
What interviewers look for
Say the reduction in one line: "it's possible exactly when, for every letter, the magazine count is at least the note count." Then mention why a 26-element array works, and that you would switch to a hash map for a larger alphabet such as Unicode.
The early exit on length is a nice touch; point it out but don't oversell it.
Follow-up questions
What if the strings could contain any Unicode characters?
Replace the 26-slot array with a hash map from character (or code point) to count. The algorithm and its O(m + n) time are unchanged, and space becomes O(k) for k distinct characters.
What if the magazine is huge and you get many different notes to check?
Count the magazine once and keep the counts. Each note is then checked in time proportional to its own length by counting the note and comparing against the stored counts, without modifying them.
What if you could only cut out whole words, not letters?
Count words instead of letters: split the magazine into words, build a word-to-count map, and spend one count per word in the note. The structure of the solution is the same.
Companies that ask Ransom Note
Ransom Note is tagged by 99 companies in our interview dataset. The score shows how often it comes up at each company.
- Infineon Technologies100%
- Thought Machine100%
- Bp100%
- Ses Satellites100%
- Evolutioniq100%
- Schlumberger100%
- Guardant Health92%
- Mozilla89%
- Momentiveai84%
- 23andme84%
- Jack Henry Associates84%
- Wepay83%
- Singtel83%
- Veracyte82%
- Envoy82%
- Zoominfo80%
- Philips80%
- Criteo78.2%
- Getyourguide78%
- Rackspace78%
- PointClickCare77%
- Snapdocs77%
- Tenable77%
- Addepar76%
and 75 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required