#383
Ransom Note
Easy Frequency count
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether the letters of magazine (each used at most once) are enough to write ransomNote.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: are the magazine's letters enough to write the note?
Why this works: count the magazine's letters and spend them; any count below zero means not enough.
Example: note "aa", magazine "aab"
a: 2 available, spend 2 → ok → true✦Hints open one at a time
Count the magazine's letters.
Spend them on the note; if any count goes negative, it's impossible.
↗Approach
Frequency array from the magazine, then decrement for every note letter and fail on a negative.
</>Solution (Java)
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] count = new int[26];
for (char c : magazine.toCharArray()) count[c - 'a']++;
for (char c : ransomNote.toCharArray()) {
if (--count[c - 'a'] < 0) return false;
}
return true;
}
}!Common mistake
Using indexOf and replacing characters in strings — slow and messy.
Complexity
- Time: O(n + m).
- Space: O(26).
Topic: Strings
🎬 Episodes 16–20: video coming soon