C++: Ransom Note

Thought Process

The problem requires determining if the ransomNote can be constructed using the letters from the magazine. To solve this, we use a hash map to count the frequency of each character in the magazine. Then, we iterate through the ransomNote and decrement the corresponding character count in the hash map. If any character in the ransomNote is not available in the magazine, we return 'false'. Otherwise, we return 'true' after successfully constructing the ransomNote. 

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        
        int hashMap[26] = {0};
        for(int i=0;i<magazine.size();i++){

            char ch = magazine[i];
            hashMap[ch-'a']++;
        }

        for(int i=0;i<ransomNote.size();i++){

            char ch = ransomNote[i];
            if(hashMap[ch-'a']>0)
                hashMap[ch-'a']--;
            else
                return false;
        }
        return true;  
    }
};

Code Complexity

Time Complexity: O(n + m)

The algorithm iterates through both the magazine and ransomNote strings once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses a fixed-size hash map (26 elements) to store character counts, making it constant in space complexity.

Code copied!