Ransom Note [Easy] — Frequency Map Check
Sanjeev SharmaAdvertisement
Problem Statement
Return true if ransomNote can be constructed using the letters from magazine (each letter used only once).
Input: ransomNote="a", magazine="b" → false
Input: ransomNote="aa", magazine="aab" → true
Solutions
C++
bool canConstruct(string r, string m) {
int cnt[26]={};
for(char c:m) cnt[c-'a']++;
for(char c:r) if(--cnt[c-'a']<0) return false;
return true;
}
Java
public boolean canConstruct(String r, String m) {
int[] cnt=new int[26];
for(char c:m.toCharArray()) cnt[c-'a']++;
for(char c:r.toCharArray()) if(--cnt[c-'a']<0) return false;
return true;
}
Python
from collections import Counter
def canConstruct(ransomNote: str, magazine: str) -> bool:
m = Counter(magazine)
for c in ransomNote:
if m[c] <= 0: return False
m[c] -= 1
return True
# One-liner: return not (Counter(ransomNote) - Counter(magazine))
JavaScript
var canConstruct = function(r, m) {
const cnt=new Array(26).fill(0);
for(const c of m) cnt[c.charCodeAt(0)-97]++;
for(const c of r) if(--cnt[c.charCodeAt(0)-97]<0) return false;
return true;
};
Complexity
- Time: O(m+r), Space: O(1)
Advertisement
