LESSON 276 OF 442 · HASH TABLE

Find the Difference in Scala: O(n) with a Mutable Map

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: e
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: y

Constraints:

0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters.

Note:

For this lesson, your algorithm should run in O(n) time, where n is the length of t.

The brute force counts each letter of t in s again and again. Count the letters of s only once, and keep the counts.

Store the counts in a mutable.Map from each letter to how many times it appears in s. Then walk through t: each letter uses up one copy from the mutable.Map. The first letter of t that has no copy left (its count is 0, or it was never there) is the extra one.

We walk through s once and t once, and each lookup in the mutable.Map is O(1) on average: O(n) time.
The mutable.Map never holds more than 26 letters, so the extra space is O(1).

STEP 1 OF 8

Guided

Ctrl + Enter to check

Find The Difference in Scala, explained

Problem overview

The string t is the string s shuffled, plus one extra lowercase letter. The method findTheDifference(s: String, t: String): Char returns that letter. For s = "abcd" and t = "abcde" it returns 'e', and for s = "" and t = "y" it returns 'y'.

This lesson asks for O(n) time, where n is the length of t. The first lesson on this problem counted a letter in both strings again and again, which costs O(n²). Here the counts are computed once and stored.

Approach: count `s` once, then spend the counts on `t`

Think of the letters of s as tokens. Walk through s and, for each letter, put one more token in that letter's pile. A mutable.Map[Char, Int] is the set of piles: the key is the letter, the value is how many tokens it has.

Now walk through t and spend one token for each letter. Because t contains every letter of s plus one more, there are enough tokens for all letters of t except the extra one. The first time a letter of t finds its pile empty, or finds no pile at all, that letter is the added one.

Take s = "aab" and t = "abaa". After counting s the map holds a -> 2 and b -> 1. Walking through t: a uses one token (a: 1), b uses one (b: 0), a uses one (a: 0), and the last a finds a count of 0. It is the extra letter, so the method returns 'a'. Note that the duplicate letter is detected even though a is in s: what matters is that its tokens ran out.

Each lookup and update in a hash map takes O(1) on average, and each string is walked once, so the total is O(n).

Step by step

Create the map. counter is a val holding a mutable Map[Char, Int]. The reference to the map never changes, but its contents do, so val is fine.
Loop over s. Each character is bound to c.
Add a token. Set counter(c) to its current count plus one. getOrElse(c, 0) supplies 0 the first time a letter is seen.
Loop over t. Again each character is bound to c.
Check for an empty pile. If counter.getOrElse(c, 0) == 0, the letter is missing from the map or its count is already used up.
Return it. That letter has more occurrences in t than in s.
Spend a token. If the pile was not empty, subtract one from counter(c). This line is only reached when the letter still has a copy left in s.
Add a fallback. After the second loop the method returns a space. The compiler requires a Char on every path, and valid input never gets there.

The solution in Scala

class Solution {
    def findTheDifference(s: String, t: String): Char = {
        val counter = scala.collection.mutable.Map[Char, Int]()
        for (c <- s) {
            counter(c) = counter.getOrElse(c, 0) + 1
        }
        for (c <- t) {
            if (counter.getOrElse(c, 0) == 0) {
                return c
            }
            counter(c) = counter.getOrElse(c, 0) - 1
        }
        return ' '
    }
}

The Scala details worth a closer look:

Mutable versus immutable maps. A plain Map in Scala is immutable, and counter(c) = ... only works on scala.collection.mutable.Map. That is why the full package name appears in the code. counter(c) = v is shorthand for counter.update(c, v).
getOrElse versus apply. counter(c) on a missing key throws a NoSuchElementException, and counter.get(c) returns an Option[Int]. getOrElse(c, 0) returns the count, or 0 when the key is missing, which is exactly the "no tokens" case. Without it, the very first counter(c) = counter(c) + 1 would fail.
Type arguments. Map[Char, Int]() creates an empty map; the type arguments are needed because there is nothing to infer them from.
return in a loop. The return c inside the for leaves the whole method. Scala 3.5 compiles it, with a warning that non-local returns are no longer supported.
Characters as keys. for (c <- s) gives Char values, matching the map's key type. Characters compare and hash by value, so equal letters always land on the same entry.

Complexity

Time: O(n). The first loop runs n - 1 times and the second at most n times. Each iteration does a constant number of map operations, which are O(1) on average.

Space: O(1). The strings hold only lowercase letters, so the map never has more than 26 entries, regardless of the length of the input.

Edge cases and common mistakes

Empty s. The map stays empty. The first character of t finds no entry, getOrElse gives 0, and the method returns that character.
The extra letter repeats a letter of s. For s = "aab" and t = "abaa" the answer is 'a'. Testing only "is this letter in the map?" would miss it; the check must be about the count reaching zero.
Forgetting the decrement. Without the second update, a letter that appears twice in both strings would never run out, and a duplicate extra letter would go unnoticed.
Indexing a missing key. Writing counter(c) + 1 instead of counter.getOrElse(c, 0) + 1 throws at run time when c is new.
Using the default Map. Importing nothing and writing Map[Char, Int]() gives an immutable map, and assigning with counter(c) = ... then doesn't compile: value update is not a member of Map[Char, Int].

Testing

s = "abcd", t = "dbeca" returns 'e'.
s = "", t = "y" returns 'y'.
s = "aab", t = "abaa" returns 'a'.
s = "z", t = "zz" returns 'z'.

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

Start learning free