Ransom Note — Solution in Python, Java & C++
Ransom Note solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Infosys.
Ransom Note is an easy coding problem on strings, hash table and counting, asked in Amazon, Infosys, Bloomberg and Apple interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Infosys, Bloomberg, Apple, Spotify
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings ransomNote and magazine, return true if ransomNote can be built using the letters of magazine.
Each letter of magazine may be used at most once.
Example 1
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2
Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: The magazine has only one a.
Example 3
Input: ransomNote = "aa", magazine = "aab"
Output: true
Constraints
1 <= ransomNote.length, magazine.length <= 40Both consist of lowercase English letters.
Hints for Ransom Note
Hint 1
Count what the magazine supplies, then spend from those counts as you read the note.
Hint 2
The moment a count would go negative, the magazine cannot cover the note.
How to solve Ransom Note
Count what the magazine supplies, then spend those counts while reading the note; a count going negative means the magazine cannot cover it.
Approach
- Tally each letter of
magazine. - For each letter of
ransomNote, decrement its count and returnfalseif it drops below zero. - Return
true.
Why it works
Each letter of the magazine can be used once, so the tally is a budget; the note is buildable exactly when no letter's demand exceeds its budget.
Complexity
- Time —
O(n + m) - Space —
O(1) — 26 counters
Pitfalls
- An early length check (
len(note) > len(magazine)→false) is a cheap short-circuit.
Reference solution
Python
def canConstruct(ransomNote: str, magazine: str) -> bool:
count = [0] * 26
for ch in magazine:
count[ord(ch) - 97] += 1
for ch in ransomNote:
idx = ord(ch) - 97
count[idx] -= 1
if count[idx] < 0:
return False
return TrueJava
public static boolean canConstruct(String ransomNote, String magazine) {
int[] count = new int[26];
for (int i = 0; i < magazine.length(); i++) count[magazine.charAt(i) - 'a']++;
for (int i = 0; i < ransomNote.length(); i++) {
int idx = ransomNote.charAt(i) - 'a';
count[idx]--;
if (count[idx] < 0) return false;
}
return true;
}C++
bool canConstruct(string ransomNote, string magazine) {
int count[26] = {0};
for (char ch : magazine) count[ch - 'a']++;
for (char ch : ransomNote) {
int idx = ch - 'a';
count[idx]--;
if (count[idx] < 0) return false;
}
return true;
}JavaScript
var canConstruct = function(ransomNote, magazine) {
const count = new Array(26).fill(0);
for (let i = 0; i < magazine.length; i++) count[magazine.charCodeAt(i) - 97]++;
for (let i = 0; i < ransomNote.length; i++) {
const idx = ransomNote.charCodeAt(i) - 97;
count[idx]--;
if (count[idx] < 0) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets