## DEV Community

Aroup Goldar Dhruba

Posted on • Updated on

# LeetCode: Ransom Note

### Problem Statement

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

### Example

Note:
You may assume that both strings contain only lowercase letters.

``````canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
``````

### Solution Thought Process

This is a well known hash map problem.

• Find the frequency of each element in the magazine, store them in a hash map.
• For each element in the ransom note, check the value in the map.
• If it doesn't exist, we can't make the ransom note.
• If it exists, then check if it's unused frequency is greater than 0.
• If it's greater than 0, then decrease the frequency to use it in the ransom note.
• If it's not greater than 0, then we have used up all of the characters available in the magazine, so we should return false.

### Solution

``````class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int>M;
bool result = true;
for(int i=0;i<magazine.size();i++)
{
if(M.find(magazine[i])==M.end())
{
M[magazine[i]]=1;
}
else {
M[magazine[i]]++;
}
}
for(int i=0;i<ransomNote.size();i++)
{
if(M.find(ransomNote[i])==M.end())
{
result = false;
break;
}
else
{
if(M[ransomNote[i]]>0)
{
M[ransomNote[i]]--;
}
else {
result = false;
break;
}
}
}
return result;
}
};
``````

### Complexity:

Time Complexity: O(m + n), where m = length of magazine and n = length of ransom note

Space Complexity: O(m) where m = length of the magazine