Start learning free

LESSON 277 OF 443 · HASH TABLE

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

    SWIFT · HASH TABLE

    Find The Difference in Swift, explained

    Problem overview

    The method findTheDifference receives strings s and t, where t is s shuffled with one extra letter added. It returns the added letter as a Character.

    For s = "abcd" and t = "abcde" the answer is "e". For s = "" and t = "y" it is "y". The extra letter can also repeat a letter that s already contains: for s = "ae" and t = "aea" it is "a".

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

    Approach: count once, then use up the copies

    The brute-force solution counts a letter in both strings again for every letter of t, and each count walks a whole string. The waste is that the counts of s never change. They can be computed once and kept.

    Build a dictionary that maps each letter to the number of times it appears in s. Then walk through t and treat the dictionary as a supply of copies: each letter of t uses up one copy of itself. Because t contains everything in s plus one more letter, every letter finds a copy to use up, except for the extra one. The first letter that finds no copy left, either because its count has dropped to 0 or because it was never in the dictionary, is the answer.

    Take s = "aab" and t = "abaa". The dictionary holds a: 2 and b: 1. Walking t: the first a uses a copy (1 left), b uses its copy (0 left), the second a uses the last copy (0 left), and the third a finds a count of 0, so it is returned.

    Each dictionary operation takes constant time on average, and each string is walked once, so the total is O(n).

    Step by step

    1. Declare the dictionary. var counter: [Character: Int] = [:] starts empty. The type annotation is needed because [:] alone doesn't say what the keys and values are.
    2. Loop over s with for c in s. Each pass gives one Character.
    3. Increment that letter's count. counter[c, default: 0] += 1 reads the count, using 0 if the letter isn't there yet, adds one and stores the result. One expression handles both the first time a letter is seen and every later time.
    4. Loop over t with another for c in t.
    5. Check for a missing copy. If counter[c, default: 0] == 0, the letter either never appeared in s or has been used up already.
    6. Return the letter. That letter is the extra one.
    7. Use up a copy. When the check fails, the letter still has a copy, so counter[c, default: 0] -= 1 removes one. This line sits after the if, so it runs only when the letter wasn't returned.
    8. Add a fallback return after the second loop. Swift requires a return on every path. The constraints guarantee that the loop always returns, so the fallback " " never runs.

    The solution in Swift

    class Solution {
    func findTheDifference(_ s: String, _ t: String) -> Character {
        var counter: [Character: Int] = [:]
        for c in s {
            counter[c, default: 0] += 1
        }
        for c in t {
            if counter[c, default: 0] == 0 {
                return c
            }
            counter[c, default: 0] -= 1
        }
        return " "
    }
}

    The Swift details worth a closer look:

    • A plain subscript returns an optional. For a dictionary of type [Character: Int], counter["z"] has type Int?: it is nil when the key is missing and Optional(1) when the value is 1. You can't add to an optional directly.
    • The default: subscript returns a plain Int. counter["z", default: 0] gives 0 for a missing key without changing the dictionary. Used with += or -=, it also inserts the key when needed. After counter["z", default: 0] += 1, a plain counter["z"] gives Optional(1).
    • Keys are Character values. Character is hashable, so it works as a dictionary key. The loop variables c are characters, matching the key type.
    • The dictionary is a value type. It belongs to this call, and nothing outside the method sees it.
    • Dictionary order is unspecified. The solution never loops over the dictionary, only over the strings, so the order doesn't matter here.

    Complexity

    Time: O(n). The first loop runs once per letter of s, which is n - 1 times, and the second loop runs at most n times. Every dictionary read or update costs constant time on average, so the total is linear in the length of t.

    Space: O(1). The dictionary holds one entry per distinct letter. The input has only lowercase English letters, so there are at most 26 entries, whatever the length of the strings.

    Edge cases and common mistakes

    • Empty s. The dictionary stays empty. The first letter of t reads a count of 0 and is returned.
    • The extra letter repeats an existing one. In s = "ae", t = "aea", the second a in t finds the count at 0. Checking only whether the key exists would miss it, which is why the test is == 0 and not "missing".
    • Decrementing before the check. If the subtraction came first, counts could go negative and the zero test would stop working. Check first, then subtract.
    • Using the plain subscript in the arithmetic. counter[c] += 1 doesn't compile, because counter[c] is an optional and += needs a plain number on the left. Use the default: form, or unwrap it yourself.
    • Returning at the end of the first loop. The answer is only known once t has been walked, so the return belongs in the second loop.

    Testing

    • s = "abcd", t = "abcde" returns "e".
    • s = "", t = "y" returns "y".
    • s = "aab", t = "abaa" returns "a".
    • s = "ae", t = "aea" returns "a".
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free