LESSON 261 OF 414 · HASH TABLE

Ransom Note in Scala: 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 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

STEP 1 OF 8

Guided

Ctrl + Enter to check

Ransom Note in Scala, explained

Problem overview

The method canConstruct(ransomNote: String, magazine: String) returns true if the note can be built from letters of the magazine, where each letter of the magazine can be used only once.

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 O(Σ) extra space, where Σ is the size of the alphabet. The map only ever holds one entry per distinct letter.

Approach: compare letter counts

The order of the letters is irrelevant, in both strings. The note "abba" can be built from "ababab" because the magazine has at least as many of each letter as the note needs. In general, the answer is true exactly when, for every letter, the magazine contains at least as many copies as the note does.

A hash map from character to count records how many times each letter occurs. Build one map for the note and one for the magazine, each with a single pass over its string. Then go through the letters and check that the note never needs more of a letter than the magazine has. Searching the magazine for each letter of the note would take O(n * m); counting makes it linear.

One map would also be enough: count the magazine, then walk through the note and use up one copy of each letter, answering false as soon as a letter has no copies left. This lesson builds two maps and compares them, which keeps the counting step identical for both strings and the check separate.

Step by step

Create two empty maps, ransomFreq and magazineFreq, as scala.collection.mutable.Map[Char, Int](). The default Map in Scala is immutable. The mutable one can be updated in place.
Count the note. A for loop goes through each character c of ransomNote. Inside it, ransomFreq(c) is set to ransomFreq.getOrElse(c, 0) + 1. A character seen for the first time starts at 0, because reading a missing key with ransomFreq(c) would throw.
Count the magazine the same way into magazineFreq. The name c exists only inside each loop, so reusing it is fine.
Loop over the alphabet. A for loop with charCode runs from 'a'.toInt to 'z'.toInt. The range written with to includes its upper bound.
Convert back to a character. val c = charCode.toChar gives the letter for the current code.
Compare. If ransomFreq.getOrElse(c, 0) is greater than magazineFreq.getOrElse(c, 0), the magazine can't supply that letter, and the method returns false. A letter missing from either map reads as 0.
Succeed. If the loop finishes without returning, every letter has enough copies, so the method returns true.

The solution in Scala

class Solution {
    def canConstruct(ransomNote: String, magazine: String): Boolean = {
        val ransomFreq = scala.collection.mutable.Map[Char, Int]()
        val magazineFreq = scala.collection.mutable.Map[Char, Int]()
        for (c <- ransomNote) {
            ransomFreq(c) = ransomFreq.getOrElse(c, 0) + 1
        }
        for (c <- magazine) {
            magazineFreq(c) = magazineFreq.getOrElse(c, 0) + 1
        }
        for (charCode <- 'a'.toInt to 'z'.toInt) {
            val c = charCode.toChar
            if (ransomFreq.getOrElse(c, 0) > magazineFreq.getOrElse(c, 0)) {
                return false
            }
        }
        return true
    }
}

The Scala details worth knowing:

Strings as collections. for (c <- ransomNote) visits the characters of the string one by one, each as a Char.
Char and Int. A Char is a number underneath. 'a'.toInt is 97 and 'z'.toInt is 122, and 98.toChar is 'b'. Looping over the codes and converting each one back is how the solution walks the alphabet.
Counting with getOrElse. m(c) = m.getOrElse(c, 0) + 1 is the standard counting idiom: the map update adds the key if it's new and replaces the count otherwise.
return inside a for. The loop body is passed to foreach as a function, so in Scala 3.5 the compiler reports a deprecation warning about non-local returns for return false. The code still works, and return leaves canConstruct. The warning points to scala.util.boundary as the replacement.
Lowercase only. The final loop checks only the letters 'a' to 'z', so the solution assumes lowercase input. A note such as "A" with the magazine "a" would return true, because the uppercase letter is never checked.

Complexity

Time: O(n + m). Counting the note takes n steps, counting the magazine takes m steps, and the final loop runs 26 times. Each map operation takes constant time on average.

Space: O(Σ). Each map holds at most one entry per distinct letter, so with a 26-letter alphabet it never exceeds 26 entries.

Edge cases and common mistakes

An empty note. "" can be built from any magazine, even "", so the result is true.
An empty magazine. "a" from "" is false.
The order doesn't matter. "abba" from "ababab" is true.
Each letter only once. Checking only that every letter of the note appears somewhere in the magazine would say true for "aa" and "abb". The counts are what make the answer false.
Reading a missing key. ransomFreq(c) throws for a letter that never appeared, so use getOrElse(c, 0).
Mixing up the two maps in the comparison. The note's count must not be greater than the magazine's.

Testing

"aa" from "abb" gives false.
"aa" from "aab" gives true.
"abba" from "ababab" gives true.
"a" from "" gives false.
"" from "" gives true.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free