Ransom Note in Swift

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 occurences of each letter in magazine and in ransomNote. How can we achieve this?

We have a data structure specially designed to do that! It is the Hash Map. We should construct two different Hash Maps:

• ransomFreq, where ransomFreq[c] is the number of occurences of letter c in ransomNote
• magazineFreq, where magazineFreq[c] is the number of occurences of letter c in magazine

How should we populate these Hash Maps?

Using a for loop, we will iterate with a variable c through every character of ransomNote and increment ransomFreq[c]. We will do the same for magazineFreq. What should we do after we have populated these hash maps?

Using a for loop, we should iterate through each character c of the alphabet (from 'a' to 'z') and check if ransomFreq[c] > magazineFreq[c]. If so, we should return false. When this loop terminates, we can conclude that the solution is valid, so we can return true