Start learning free

LESSON 271 OF 437 · HASH TABLE

Find the Difference in C++: O(n) with unordered_map

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

    C++ · HASH TABLE

    Find The Difference in C++, explained

    Problem overview

    The string t is the string s shuffled, with one extra lowercase letter inserted somewhere. findTheDifference returns that extra letter as a char. The string s may be empty, and t is always one character longer than s.

    For s = "abcd" and t = "abcde" the answer is 'e': the letters a to d each appear once in both strings, and e has no partner. For s = "" and t = "y" the answer is 'y'.

    This lesson asks for O(n) time, where n is the length of t.

    Approach: build a frequency map, then spend it

    The brute-force way recounts a letter in both strings for every character of t, which is O(n²). The slow part is the repeated counting. Counting every letter of s once, up front, removes it.

    Walk s once and store, for each letter, how many copies it has. This is a frequency map. Then walk t and treat each stored copy as a token: each letter of t uses up one copy of itself. Because t is a shuffle of s plus one letter, every letter finds a token except the extra one. When a letter of t finds its count at 0 (or finds nothing at all), it is the extra letter.

    Take s = "aab" and t = "abaa". The map after the first loop is a: 2, b: 1. Walking t: the first a uses one token (a: 1), b uses its only token (b: 0), the second a uses the last a token (a: 0), and the third a finds 0, so 'a' is returned. This also shows why a plain "is it in s?" check isn't enough: the extra letter can be a duplicate of a letter that is in s.

    The cost is two passes over the strings, each step a hash lookup, so O(n) on average. A later lesson removes the map entirely with XOR.

    Step by step

    1. Declare an unordered_map<char, int> named counter. The keys are letters and the values are how many copies of each remain.
    2. Loop over s with a range-based for, naming the character c.
    3. Increment counter[c]. A missing key is created with the value 0 by operator[], so the first sight of a letter works without a special case.
    4. Loop over t, again naming the character c.
    5. Check whether counter[c] == 0. That covers both a letter that isn't in the map and one whose copies are all used up.
    6. Return c inside that if: it is the extra letter.
    7. Otherwise decrement counter[c]. This line is reached only when a copy exists, so a count never goes below zero.
    8. Return a fallback character after the loop. The constraints guarantee that the loop returns first, but a function with a return type must return on every path.

    The solution in C++

    class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char, int> counter;
        for (char c : s) {
            counter[c]++;
        }
        for (char c : t) {
            if (counter[c] == 0) {
                return c;
            }
            counter[c]--;
        }
        return ' ';
    }
};

    C++ details worth a closer look:

    • operator[] inserts. Reading counter[c] for a missing key adds c with the value 0. That is what makes counter[c]++ work on the first sight of a letter. It also means the check counter[c] == 0 in the second loop may insert an entry, which is harmless here because the function returns right away. When you want to look without inserting, use find or count.
    • Values are zero-initialised. A new int value created by operator[] is 0, so you never read garbage.
    • Two loops, two different c variables. Each char c is scoped to its own loop, so reusing the name is legal.
    • The strings are copies. s and t are taken by value, which is fine at 1000 characters. Nothing in the method changes them.
    • The fallback. Running off the end of a non-void function is undefined behaviour, so the final return ' '; closes the path even though valid input never reaches it.

    Complexity

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

    Space: O(1) in practice, O(k) in general. The map has one entry per distinct letter in s, and the input holds only lowercase letters, so there are at most 26 entries. Counting the map as proportional to the number of distinct characters is the precise statement.

    Edge cases and common mistakes

    • Empty s. The map stays empty, the first letter of t reads 0, and it is returned.
    • The extra letter repeats a letter of s. With s = "a" and t = "aa" the first a uses the only token and the second finds 0, so the answer is 'a'.
    • Decrementing before checking. If the decrement came first, the counts would go negative and the zero test would never fire for a duplicate. Check first, then decrement.
    • Counting t in the first loop. The map must be built from s only. Counting both strings into the same map would never produce a zero for the extra letter.
    • Returning inside the first loop. The extra letter is only discovered while walking t.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "aab", t = "abaa" gives 'a'.
    • s = "xyz", t = "zyxq" gives 'q'.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free