Start learning free

LESSON 238 OF 348 · HASH TABLE

Ransom Note in Kotlin: O(n + m) with Letter Counts in a HashMap

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

    KOTLIN · HASH TABLE

    Ransom Note in Kotlin, explained

    Problem overview

    The function canConstruct receives two strings, ransomNote and magazine. It returns true if the note can be built from letters of the magazine, and false otherwise. Each letter in the magazine can be used only once, and the order of the letters doesn't matter.

    With ransomNote = "aa" and magazine = "abb" the answer is false: the note needs two as, and the magazine has one. With magazine = "aab" the answer is true. The statement asks for O(n + m) time and extra space that depends only on the alphabet size, not on the string lengths.

    Approach: compare letter counts

    The order of letters never matters, only how many of each letter are available and how many are needed. So the note can be built exactly when, for every letter, the magazine has at least as many copies as the note.

    Checking this by searching the magazine for each note letter and crossing it out would take O(n * m) time. Counting is faster. Build one frequency map for the note and one for the magazine, each from letter to count, in a single pass over each string. Then compare the two counts letter by letter. Since each pass is linear and the comparison covers a fixed alphabet, the total is O(n + m).

    For "aa" and "abb" the note map is {a=2} and the magazine map is {a=1, b=2}. The note needs 2 as, the magazine has 1, so the answer is false. For "abba" and "aaabbb" the maps are {a=2, b=2} and {a=3, b=3}. Every count in the note is at most the magazine's count, so the answer is true, and the leftover letters are simply unused.

    Step by step

    1. Create the two maps. ransomFreq and magazineFreq are each a HashMap<Char, Int>. They're vals because the references never change, though the contents do.
    2. Loop over the note. for (c in ransomNote) visits each character in turn.
    3. Count each letter. Store getOrDefault(c, 0) + 1 under c. The default makes a letter that is seen for the first time start from 0.
    4. Loop over the magazine the same way. Reusing the name c is fine, since each loop variable exists only inside its loop.
    5. Count the magazine's letters into magazineFreq.
    6. Walk the alphabet. Declare a new var c = 'a' and loop with while (c <= 'z'). This variable is separate from the earlier loop variables.
    7. Compare counts. If the note's count for c is greater than the magazine's, return false. Both lookups use getOrDefault(c, 0), because a letter that never occurred is simply missing from the map.
    8. Move to the next letter with c++. Without it the loop would never end.
    9. Return true after the loop. Every letter had enough copies.

    The solution in Kotlin

    class Solution {
    fun canConstruct(ransomNote: String, magazine: String): Boolean {
        val ransomFreq = HashMap<Char, Int>()
        val magazineFreq = HashMap<Char, Int>()
        for (c in ransomNote) {
            ransomFreq[c] = ransomFreq.getOrDefault(c, 0) + 1
        }
        for (c in magazine) {
            magazineFreq[c] = magazineFreq.getOrDefault(c, 0) + 1
        }
        var c = 'a'
        while (c <= 'z') {
            if (ransomFreq.getOrDefault(c, 0) > magazineFreq.getOrDefault(c, 0)) {
                return false
            }
            c++
        }
        return true
    }
}

    Kotlin details worth knowing:

    • Iterating a string. for (c in text) gives each character as a Char. A Char is written with single quotes, 'a', and a String with double quotes.
    • Reading a map gives a nullable. ransomFreq[c] has type Int? and is null for a missing key, so it can't be used in arithmetic. getOrDefault(c, 0) returns a plain Int.
    • Char supports comparison and ++. c++ moves to the next character code, so from 'a' it reaches 'b', and after 'z' comes '{', which ends the while loop since it is greater than 'z'.
    • Shadowing. The variable c in var c = 'a' is declared after both for loops have ended, so it doesn't clash with their loop variables.
    • val on a map. It stops the name from being reassigned, but ransomFreq[c] = ... still changes the map.

    Complexity

    Let n be the length of ransomNote and m the length of magazine.

    Time: O(n + m). Each counting loop is linear in its string, and each map update is O(1) on average. The alphabet loop runs 26 times, a constant.

    Space: O(Σ), where Σ is the alphabet size. Each map holds at most one entry per distinct letter, so with lowercase letters that is at most 26 entries per map, whatever the string lengths.

    Edge cases and common mistakes

    • Empty note. An empty ransomNote can always be built, so the answer is true, even from an empty magazine.
    • Magazine too short. If the note is longer than the magazine, some letter must be short, and the answer is false.
    • Counting only presence. Checking that each letter occurs, instead of how many times, wrongly accepts "aa" with "ab".
    • Extra letters. Letters in the magazine that the note doesn't use are fine.
    • Order. "ab" from "ba" is true.
    • Letters outside 'a' to 'z'. This solution compares only lowercase letters, so it assumes the inputs hold only those. Given "A" and "a", it would return true, because uppercase letters and digits are never compared. To handle any characters, loop over the note's own map entries instead of the alphabet.
    • Not defaulting. Using ransomFreq[c] + 1 without a default doesn't compile.

    Testing

    • ransomNote = "aa", magazine = "abb" gives false.
    • ransomNote = "aa", magazine = "aab" gives true.
    • ransomNote = "ab", magazine = "ba" gives true.
    • ransomNote = "", magazine = "" gives true.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free