Problem Statement

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints:

• 1 <= ransomNote.length, magazine.length <= $10^5$

• ransomNote and magazine consist of lowercase English letters.

Implementation

Decoding the question

If ransom note is bigger than magazine, then its not possible to create a substring. So, return false.

I am looking for a way where I can use the occurrence count of each letter of ransom note and match it with magazine's each letter occurrence count.

Suppose I take the letter "a" from ransom note and store the occurrences of "a" in a map, and while I traverse through magazine I will also store the occurrence of "a" in another map.

If count of magazine's "a" is greater than or equal to ransom's "a" count then we can create the word, else return false.

Solution I

Using HashMap

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
        if(ransomNote.length === 0 || magazine.length === 0) {
                return false;
        }

        if(ransomNote.length > magazine.length) {
            return false;
        }

        //  { key : character , value: countOfOccurrence};
    let hasMap = {};
        // 1st: Create the Map with magazine's character occurrence and count.

        for(let m = 0; m < magazine.length; m++) {
                const magChar = magazine[m];
                if( hasMap[magChar] !== undefined ) {
                    hasMap[magChar] += 1;
                } else {
                    hasMap[magChar] = 1;
                }
        }
/*

         Now your map has been created 
         So, now you have to:

            1. find values of ransom note's characters in the map        
            2. Reduce the count of the character(key)'s value by 1
            3. Check if the count of the character is 0 or less than 0
            4. If its less than 0, clearly ransom note can't be made.
*/

    let isPossible = true;

    for(let r = 0; r < ransomNote.length; r++ ) { 
            const ranChar = ransomNote[r];
            if(hasMap[ranChar]) {
                hasMap[ranChar] -= 1 ;
                if(hasMap[ranChar] < 0) {
                    isPossible = false;
                    break;
                }
            } else {
                    isPossible = false;
                    break;
                }
    }

    return isPossible;

};

Results

Conclusion

I hope you got a new perspective of solving this problem easy in O(n) time complexity.

If you are JavaScript Developer and want to get into top tech company, follow me on Twitter.

👇🏻👇🏻

https://twitter.com/sagars_01

I tweet and write about Data Structures and Algorithms, System Design and Large Scale Systems.