Start learning free

LESSON 279 OF 445 · HASH TABLE

Find the Difference in Rust: O(n) with a HashMap

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

STEP 1 OF 8

Guided

Ctrl + Enter to check

RUST · HASH TABLE

Find The Difference in Rust, explained

Problem overview

The function find_the_difference takes two string slices. The string t is a shuffle of s with one extra lowercase letter added at a random position. The function returns the added letter as a char. The string s may be empty.

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

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

The brute-force answer counts each letter of t inside s again and again, which costs O(n²). The waste is that the counts of s never change, so they can be computed once and kept.

Build a HashMap from each letter to the number of times it appears in s. Then walk through t and treat the map as a stock of letters: each letter of t uses up one copy. Because t is s plus one letter, every letter of t finds a copy until the extra one shows up. The extra letter either has no entry in the map or has an entry whose count has already dropped to 0. The first such letter is the answer.

Take s = "ab" and t = "bba". The map starts as a: 1, b: 1. The first b uses the copy of b and the count falls to 0. The second b finds a count of 0, so it is the extra letter and the function returns 'b'.

Step by step

Create the map. A HashMap<char, i32> named counter, made with HashMap::new() and declared mut, because it will be filled.
Loop over s.chars() with the variable c.
Increment the entry for c. The entry API handles the first sighting and the later ones in one line: entry(c) finds the slot, or_insert(0) creates it with 0 when it is missing, and the result is a mutable reference that the * and += 1 update.
Loop over t.chars() in the same way.
Check for a copy. Look the letter up with get, and treat a missing key as 0. If the stock is 0, no copy is left.
Return the letter when there is no copy left. That is the extra letter.
Otherwise spend a copy by decrementing the entry. This line runs only for letters that still had stock.
End with a placeholder character as the final expression. The constraints guarantee the loop returns first, but the function must still produce a char on every path.

The solution in Rust

use std::collections::HashMap;

impl Solution {
    fn find_the_difference(s: &str, t: &str) -> char {
        let mut counter: HashMap<char, i32> = HashMap::new();
        for c in s.chars() {
            *counter.entry(c).or_insert(0) += 1;
        }
        for c in t.chars() {
            if counter.get(&c).copied().unwrap_or(0) == 0 {
                return c;
            }
            *counter.entry(c).or_insert(0) -= 1;
        }
        ' '
    }
}

On ("abcd", "abcde") it returns 'e', and on ("xyz", "zyxq") it returns 'q'.

The Rust details worth a closer look:

use std::collections::HashMap; brings the type into scope. HashMap isn't in the prelude, so without the line the name is unknown.
get returns an Option. counter.get(&c) is Option<&i32>: Some(2) for a key holding 2, and None for a missing key. It takes a reference to the key, hence &c.
copied() and unwrap_or(0). copied() turns Option<&i32> into Option<i32> by copying the number out of the reference, and unwrap_or(0) supplies 0 for None. Together they say "the count, or 0 if the letter was never seen" without any panic.
Indexing would panic. Writing counter[&c] for a missing key panics instead of returning an option, which is why the lesson uses get.
entry().or_insert(0). It returns &mut i32. The leading * dereferences it so that += and -= change the stored number, not the reference.
The final ' ' has no semicolon, so it is the function's return value when no earlier return fires.

Complexity

Time: O(n). The first loop visits the n - 1 letters of s and the second visits at most n letters of t. Each map operation takes O(1) on average.

Space: O(1). The map holds at most one entry per distinct letter, and the input has only 26 lowercase letters, so its size has a fixed upper bound however long the strings are.

Edge cases and common mistakes

Empty s. The map stays empty, so the first letter of t has no entry, reads as 0 and is returned. ("", "y") gives 'y'.
The extra letter is a repeat. For ("aa", "aaa"), the third a finds the count at 0 after two copies are used. Checking only whether the key exists would miss it, which is why the test is "count is 0", not "key is missing".
Decrementing before checking. If the decrement ran first, the count would go to -1 for the extra letter and the check would never see a 0. The check comes first.
Using the type u32 for counts. Decrementing below 0 would panic in a debug build, and wrap in an optimized one. Here the check stops the decrement before the count goes below 0, but i32 avoids the question.
Missing mut. The map is modified in both loops, so it must be declared mut.

Testing

s = "abcd", t = "abcde" gives 'e'.
s = "", t = "y" gives 'y'.
s = "ab", t = "abb" gives 'b'.
s = "aa", t = "aaa" gives 'a'.
s = "xyz", t = "zyxq" gives 'q'.

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

Start learning free