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