Start learning free

LESSON 272 OF 438 · HASH TABLE

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

    PYTHON · HASH TABLE

    Find The Difference in Python, explained

    Problem overview

    The method findTheDifference receives two strings. The string t is a shuffle of s with one extra lowercase letter inserted somewhere, and the method returns that extra letter. The string s can be empty, and t is always exactly one character longer than s.

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

    Approach: count s once, then use the counts up

    A simple solution counts every letter of t inside both strings with count(). Each call reads a whole string, so the total is O(n²). The waste is that the same counts are recomputed again and again.

    The faster idea computes the counts of s once and stores them in a dictionary that maps each letter to how many times it occurs in s. Then the method walks through t and treats the dictionary as a supply of letters. Each letter of t uses up one copy. Every letter that came from s finds a copy waiting. The extra letter is the one that finds none: either it never appeared in s, or all its copies were already used by earlier occurrences in t.

    Take s = "ab" and t = "aba". The dictionary starts as {'a': 1, 'b': 1}. The first a uses the only a, leaving 0. The b uses the only b. The second a finds a count of 0, so it is the extra letter.

    Walking through s once and t once, with average O(1) dictionary operations, gives O(n) time.

    Step by step

    1. Create an empty dictionary named counter. It will hold the number of occurrences of each letter of s.
    2. Loop over s with the variable c, to visit every letter once.
    3. Increment the count. A letter seen for the first time has no entry yet, so the code reads the current count with a default of 0 and adds one.
    4. Loop over t with a second loop, again using c.
    5. Check for a missing copy. If the dictionary has no copy of c left, either because the letter is missing or because its count is 0, then this letter has no partner in s.
    6. Return it. That letter is the answer, so the method returns immediately.
    7. Use up a copy. If the check did not fire, the letter has a partner, so its count goes down by one. Only letters that are in the dictionary reach this line.
    8. Add a fallback return after the second loop. With valid input the method always returns inside the loop, but the fallback keeps every path returning a string.

    The solution in Python

    class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        counter = {}
        for c in s:
            counter[c] = counter.get(c, 0) + 1
        for c in t:
            if counter.get(c, 0) == 0:
                return c
            counter[c] -= 1
        return ' '

    Python details worth knowing:

    • dict.get(key, default). counter.get(c, 0) returns the stored count, or 0 when c is not a key. Plain counter[c] would raise a KeyError for a missing key, so the first loop needs get to start counting a new letter.
    • The same check covers two cases. A letter that is not in the dictionary and a letter whose count has dropped to 0 both give 0 from get, so one comparison handles both.
    • Why counter[c] -= 1 is safe. It runs only after the check has shown the count is not 0, which means c is a key with a positive count. It never raises a KeyError, and the count never goes below 0.
    • Dictionary size. Keys are lowercase letters, so the dictionary holds at most 26 entries.

    Complexity

    Time: O(n). The first loop runs n - 1 times and the second at most n times. Each dictionary read or write takes O(1) on average, so the total is linear.

    Space: O(1). The dictionary can hold only the 26 lowercase letters, however long the strings are.

    Edge cases and common mistakes

    • Empty s. The dictionary stays empty, the first letter of t gets 0 from get, and it is returned. For t = "y" the result is "y".
    • The extra letter duplicates an existing one. The extra a in t = "aba" is caught by the count reaching 0, not by the letter being absent. A solution that only tests membership misses it.
    • The extra letter is not the last one. s = "abcd" and t = "abecd" returns "e" from the middle of the loop. The method returns at the first letter with no copy left, which is right because exactly one letter is extra.
    • Indexing instead of get. Writing counter[c] + 1 in the first loop raises a KeyError on the first letter.

    Testing

    • s = "abcd", t = "abcde" gives "e".
    • s = "", t = "y" gives "y".
    • s = "ab", t = "aba" gives "a".
    • s = "abcd", t = "dcbae" gives "e".
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free