Start learning free

LESSON 272 OF 438 · HASH TABLE

Find the Difference in JavaScript: O(n) with a Frequency Object

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 7
    Ctrl + Enter to check

    JAVASCRIPT · HASH TABLE

    Find The Difference in JavaScript, explained

    Problem overview

    The method findTheDifference(s, t) receives two strings of lowercase letters. The string t is s shuffled, with one extra letter added at some position. The method returns the extra letter as a one-character string.

    For s = "abcd" and t = "abcde" the answer is "e". For s = "" and t = "y" the answer is "y". The string s can be empty, and t is always one character longer.

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

    Approach: count s once, then use the counts up

    The brute-force version counts a letter in both strings every time it meets that letter in t, and that repeated work makes it O(n²). The fix is to count the letters of s a single time and keep the result in a lookup table: an object that maps each letter to the number of times it appears in s.

    Then walk through t. Each letter of t uses up one copy from the table. Every letter of s has its partner in t, so those letters always find a copy to use. The extra letter is the one that finds none: either its count has already dropped to 0, or it was never in the table.

    Here is s = "aab" and t = "abaa". The table from s is { a: 2, b: 1 }. Walking through t:

    1. a has 2 copies. Use one: { a: 1, b: 1 }.
    2. b has 1 copy. Use it: { a: 1, b: 0 }.
    3. a has 1 copy. Use it: { a: 0, b: 0 }.
    4. a has 0 copies left, so a is the extra letter.

    The method can stop at that moment. It never needs to look at the rest of t.

    Step by step

    1. Create an empty object named counter with const. The variable never gets reassigned, only its contents change, so const is right.
    2. Loop over s with for...of, which gives one character at a time.
    3. Add one to the letter's count. A letter seen for the first time has no entry, and reading a missing key gives undefined, so the code reads the count as (counter[c] || 0): the stored number, or 0 when there is none. Then it adds 1 and stores the result back.
    4. Loop over t in a second for...of. The first loop must be completely finished before this one starts, so that the table is complete.
    5. Check !counter[c]. The value is falsy in two cases: the letter has no entry (undefined), or its count has reached 0. Both mean "no copy left".
    6. Return c in that case: this is the extra letter.
    7. Decrement counter[c]. This line is reached only when a copy was available, so the count can't go below zero.

    The solution in JavaScript

    class Solution {
    findTheDifference(s, t) {
        const counter = {};
        for (const c of s) {
            counter[c] = (counter[c] || 0) + 1;
        }
        for (const c of t) {
            if (!counter[c]) {
                return c;
            }
            counter[c]--;
        }
    }
}

    Some JavaScript details worth a closer look:

    • A plain object as a table. The letters become property names, and counter["a"] and counter.a mean the same thing. After the first loop on "abcd", counter is { a: 1, b: 1, c: 1, d: 1 }.
    • A missing key is undefined, not an error. counter.z on that object is undefined, and !counter.z is true. That is why a single check covers both "never seen" and "used up".
    • || 0 versus ?? 0. Here the two behave the same, because a stored count is never 0 at that point in the first loop. The || operator replaces every falsy value, while ?? replaces only undefined and null. With counts, ?? is the more precise habit.
    • A Map would also work. It would use map.get(c) and map.set(c, ...). For lowercase letters the plain object is shorter and works fine.
    • No final return. If the loop ended without finding anything, the method would return undefined. With valid input, the extra letter always stops the loop first.

    Complexity

    Time: O(n). The first loop walks s, which has n - 1 letters, and the second loop walks at most t, which has n letters. Each step reads or writes one property of the object, which takes constant time on average. Two passes of constant work per letter is O(n).

    Space: O(1). The object holds one entry per distinct letter, and the input only has lowercase letters, so it never has more than 26 entries, no matter how long the strings are.

    Edge cases and common mistakes

    • An empty s. The first loop does nothing, so counter stays empty. The first letter of t finds no entry, and the method returns it. For t = "y" that is "y".
    • The extra letter is a duplicate. For s = "aab" and t = "abaa" the answer is "a". A check such as "is this letter missing from s?" would not find it, but the table does, because the count of a reaches 0.
    • The extra letter is new. For s = "ab" and t = "abz" there is no entry for z, so the check !counter[c] is true on that letter and "z" is returned.
    • Forgetting the decrement. Without counter[c]--, the counts never go down and the second loop never finds a letter to return.
    • Using the table the wrong way round. Counting t first and walking s would find a letter with too many copies in s, and there is none. The loop that returns must walk the longer string, t.
    • Using if (counter[c] === 0) only. That misses letters that are not in the table, where the value is undefined, not 0.

    Testing

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