Ransom Note

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

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

Let's take the two examples given in the statement and solve them "by hand". In both examples, ransomNote consists of two 'a's. Which means we need to have at least two 'a's in magazine to be able to construct the solution. In the first example, we have only one 'a' in magazine and that's why we return false while in the second example, we have two of them, so that's why we return true. Pretty simple. Now what if ransomNote also contains letter 'b'? What property should be satisfied to return true? Take some small examples on paper and try to figure it out.

Let's take ransomNote = "abba". We need at least two 'a's and two 'b's in magazine to be able to construct the solution. First observation is that the order of letters in ransomNote is not important. The requirement is the same also for ransomNote = "aabb" or ransomNote = "abba". The same holds true for magazine. It doesn't matter if magazine = "aaabbb" or magazine = "ababab", both are good as the conditions are satisfied:

• 'a' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
• 'b' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)

All these being said, can you figure out what condition should be satisfied to return true for the general case?

The condition is that for each letter of the alphabet (from 'a' to 'z'), the letter should appear in magazine at least the same number of times it does in ransomNote. So we need to separately count the number of occurrences of each letter in magazine and in ransomNote. How can we achieve this?

We have a data structure specially designed to do that: a frequency table, such as a Hash Map (or, since the letters are only 'a' to 'z', a 26-slot array). We can build two frequency tables:

• one for ransomNote, where the entry for letter c is the number of occurrences of c in ransomNote
• one for magazine, where the entry for letter c is the number of occurrences of c in magazine

How should we populate these tables?

Using a loop, we will go through every character c of ransomNote and increment the entry for c in its table. We will do the same for magazine. What should we do after we have populated these tables?

Using a loop, we should go through each character c of the alphabet (from 'a' to 'z') and check if the count of c in ransomNote is greater than its count in magazine. If so, we should return false. When this loop terminates, we can conclude that the solution is valid, so we can return true