#   # 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.

👇🏻👇🏻