Start learning free

LESSON 276 OF 442 · HASH TABLE

Find the Difference in Go: O(n) with a Map of Counts

Practice O(n) Read the full explanation

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 map from each letter to how many times it appears in s. Then walk through t: each letter uses up one copy from the 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 map is O(1) on average: O(n) time.
The map never holds more than 26 letters, so the extra space is O(1).

STEP 1 OF 8

Guided

Ctrl + Enter to check

GO · HASH TABLE

Find The Difference in Go, explained

Problem overview

The string t is the string s shuffled, with one extra lowercase letter added at a random position. findTheDifference(s string, t string) returns the extra letter as a rune. The string s can be empty, and t is always exactly one letter longer.

For s = "abcd" and t = "abcde" the answer is 'e'. For s = "" and t = "y" it is 'y'. This lesson asks for O(n) time, where n is the length of t.

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

The brute-force solution counts a letter in both strings for every letter of t, which makes it O(n²). Most of that work repeats. A letter that occurs five times in t is counted five times in each string.

A map removes the repetition. Walk through s once and record how many copies of each letter it contains. Then walk through t and treat the map as a supply of copies: every letter of t uses up one copy. Every letter of t that came from s finds a copy waiting. The extra letter is the one that finds none, because its supply ran out, or because s never held it.

Take s = "aab" and t = "abaa". The map from s is a: 2, b: 1. Reading t: the first a leaves 1 copy, b leaves 0, the second a leaves 0. The last a finds a count of 0, so it is the extra letter.

Step by step

Create the map with make(map[rune]int) and store it in counter. The keys are letters (runes) and the values are the number of unused copies.
Loop over s with for _, c := range s, discarding the index.
Count each letter with counter[c]++. A key that isn't in the map reads as 0, so the first sighting of a letter works without any special case.
Loop over t the same way.
Test for an exhausted supply with counter[c] == 0. This one comparison covers two situations: the letter is missing from the map, or its count has already dropped to 0.
Return the letter when the test succeeds. It is the extra one.
Otherwise spend a copy with counter[c]--. The order matters: the test comes before the decrement.
Add the fallback return after the loop. Go needs a return on every path, although the guarantee about t means the loop always returns first.

The solution in Go

func findTheDifference(s string, t string) rune {
    counter := make(map[rune]int)
    for _, c := range s {
        counter[c]++
    }
    for _, c := range t {
        if counter[c] == 0 {
            return c
        }
        counter[c]--
    }
    return ' '
}

The Go details worth a closer look:

A missing key gives the zero value. Reading counter['z'] from a map that has no 'z' returns 0 and does not add the key. Because of this, counter[c]++ and counter[c] == 0 are both safe on a letter that was never stored. To tell "absent" from "present with 0", use the two-value form n, ok := counter[c]. This solution doesn't need the difference.
Always create the map. A variable declared as var counter map[rune]int is a nil map. Reading from it works and returns 0, but writing to it panics with assignment to entry in nil map. make gives a usable map.
range over a string yields runes. The loop variable c is a rune, which is why the map's key type is rune and the function can return c directly. Indexing, s[i], would give bytes instead, a different type.
Printing the result. A rune is an integer. fmt.Println shows 101 for 'e', while string(r) or fmt.Printf("%c", r) shows the letter.
Map order doesn't matter here. Go iterates a map in a random order, but this solution never iterates the map. It only looks up and updates single keys.

Complexity

Time: O(n). The first loop runs over s and the second over t, which together are about 2n steps. Each map read or write takes O(1) on average.

Space: O(1). The strings hold lowercase letters only, so the map never has more than 26 entries, no matter how long the strings are. Its size is bounded by the alphabet, not by n. A plain array of 26 counters would work the same way, but the map keeps the code short and doesn't depend on the letters' codes.

Edge cases and common mistakes

Empty s. The map stays empty, and the only letter of t finds a count of 0, so it is returned.
The extra letter repeats a letter of s. s = "aab", t = "abaa" returns a. The count catches it on the third a, even though a is in the map.
Decrementing before testing. If the decrement runs first, a count of 0 becomes -1 and the test == 0 never fires for that letter. Test first, then decrement.
Counting t as well. Building maps for both strings and comparing them works, but it uses more code than a single map that is spent down.
Forgetting the nil map. Declaring the map with var and no make panics on the first counter[c]++.

Testing

s = "abcd", t = "abcde" gives e.
s = "", t = "y" gives y.
s = "aab", t = "abaa" gives a.

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

Start learning free