Start learning free

LESSON 234 OF 338 · HASH TABLE

Ransom Note in Go: O(n + m) with Frequency Maps

Practice O(n + m) Read the full explanation

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 = "aa", magazine = "abb"
Output:  false

Example 2:

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

Note:

Your algorithm should run in O(n + m) time and use O(Σ) extra space.


Hints:

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

STEP 1 OF 9
    Ctrl + Enter to check

    GO · HASH TABLE

    Ransom Note in Go, explained

    Problem overview

    The function canConstruct takes two strings, ransomNote and magazine. It returns true if the note can be assembled from letters of the magazine, where each magazine letter can be used at most once, and false otherwise. The order of letters does not matter, only how many of each are available.

    With ransomNote = "aa" and magazine = "abb" the answer is false: the note needs two a's and the magazine has one. With magazine = "aab" the answer is true, and the leftover b is simply unused.

    The statement asks for O(n + m) time, where n and m are the string lengths, and O(Σ) extra space, where Σ is the alphabet size (26 lowercase letters here).

    Approach: compare letter counts

    Trying to cross letters off the magazine one by one would rescan the magazine for each note letter, which is O(n * m). Because order is irrelevant, the whole question reduces to one condition: for every letter, the magazine contains at least as many copies as the note. So count the letters of each string once, then compare the counts letter by letter.

    A hash map from letter to count is the natural tool. Reading a missing key returns 0, so a letter that never appears in a string needs no special handling, neither when counting nor when comparing.

    Take ransomNote = "abba" and magazine = "ababab". The note's counts are a: 2 and b: 2. The magazine's counts are a: 3 and b: 3. For a, 2 is not greater than 3; for b, 2 is not greater than 3; every other letter reads 0 against 0. No letter comes up short, so the answer is true. Change the magazine to "abbb" and a has only 1 copy against the note's 2, so the answer becomes false.

    The same result could be had with a single map: count the magazine, then walk through the note and decrement, failing if a count drops below zero. This lesson keeps two maps because the comparison is then easy to read and to check.

    Step by step

    1. Create two maps with make, ransomFrequency and magazineFrequency, each of type map[rune]int. The key is a rune because ranging over a Go string produces runes.
    2. Count the note. Range over ransomNote, discard the index with _, and increment ransomFrequency[character].
    3. Count the magazine the same way into the second map. Reusing the name character is fine, because each loop variable exists only inside its own loop.
    4. Loop over the alphabet with character going from 'a' to 'z'.
    5. Compare the counts. If the note needs more copies of a letter than the magazine has, return false immediately: one short letter is enough to make the note impossible.
    6. Return true after the loop, since no letter came up short.

    The solution in Go

    func canConstruct(ransomNote, magazine string) bool {
    ransomFrequency := make(map[rune]int)
    magazineFrequency := make(map[rune]int)
    for _, character := range ransomNote {
        ransomFrequency[character]++
    }
    for _, character := range magazine {
        magazineFrequency[character]++
    }
    for character := 'a'; character <= 'z'; character++ {
        if ransomFrequency[character] > magazineFrequency[character] {
            return false
        }
    }
    return true
}

    The Go details:

    • range over a string yields runes. Each iteration gives the byte offset and the character as a rune (an alias for int32), decoded from UTF-8. For "aé" the offsets are 0 and 1, and the rune values are 97 and 233. Indexing instead, s[i], gives a single byte, and é occupies two bytes.
    • Why make. A map that is only declared is nil, and writing to it panics. make(map[rune]int) creates a usable empty map.
    • Increment of a missing key. ransomFrequency[character]++ reads 0 for an absent key, adds one and stores the result.
    • A character literal is a rune. The type of 'a' is rune, so character := 'a' declares a rune that can be compared with <= and incremented with ++, and it matches the map's key type.
    • Comparing an absent letter. A letter absent from the note reads as 0 in ransomFrequency, and 0 is never greater than a count, so it cannot cause a false.

    Complexity

    Time: O(n + m). Counting the note takes n steps, counting the magazine takes m steps, and the alphabet loop runs 26 times, a constant. Map operations are O(1) on average.

    Space: O(Σ). Each map holds at most one entry per distinct letter, which is bounded by the alphabet size and not by the string lengths.

    Edge cases and common mistakes

    • Empty note. canConstruct("", "abc") and canConstruct("", "") are true: nothing is needed.
    • Empty magazine. canConstruct("a", "") is false.
    • Counting with a set. A set would only record that a letter exists, so "aa" against "ab" would wrongly pass. The counts are what matter.
    • Comparing the wrong direction. The failing condition is note count greater than magazine count. A magazine with extra letters is fine.
    • Letters outside a to z. The final loop only inspects lowercase ASCII letters, which is what the problem's inputs consist of. With this solution, canConstruct("A", "a") would return true because the uppercase letter is never compared. If other characters were possible, loop over the keys of ransomFrequency instead.

    Testing

    • "aa", "abb" gives false.
    • "aa", "aab" gives true.
    • "abba", "ababab" gives true.
    • "", "abc" gives true.
    • "a", "" gives false.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free