Start learning free

LESSON 222 OF 442 · BRUTE FORCE

Find the Difference in TypeScript: Brute Force with Counting

Practice O(n2) 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.

The extra letter has to be a letter that appears in t. So we can iterate through every character of t and ask: "is this the extra one?"

A character i is the extra one if and only if it appears more times in t than in s. We can compare the count of i in both strings.

We'll write a small helper countChar(str: string, ch: string): number that loops through str and tallies matches. Then we can use it like: 
for (const i of t) {
    if (this.countChar(s, i) !== this.countChar(t, i)) {
        return i;
    }
}


This brute-force approach is O(n2) because each countChar call walks the whole string, and we do it for every character. It's the simplest place to start; later solutions improve to O(n).
STEP 1 OF 9
    Ctrl + Enter to check

    TYPESCRIPT · BRUTE FORCE

    Find The Difference in TypeScript, explained

    Problem overview

    The method findTheDifference receives two strings. t contains every letter of s, shuffled, plus exactly one extra letter somewhere. The method returns that extra letter. Both strings use lowercase English letters only, and s can be empty.

    For s = "abcd" and t = "abcde" the answer is "e": every other letter appears once in each string. For s = "" and t = "y" the answer is "y", because nothing in t has a partner in the empty string.

    Approach: compare letter counts

    Because t is s plus one letter, the extra letter is the only one that appears more times in t than in s. Every other letter appears the same number of times in both. So the plan is to look at each letter of t, count it in s, count it in t, and return the first letter where the two counts differ.

    This is the simplest correct idea, and it is a brute force: counting a letter means walking a whole string, and the loop does that for every letter of t. With n as the length of t, that is about n letters times two walks of up to n characters, so O(n²) time. The two other lessons on this problem remove the repeated walks, first with a table of counts and then with XOR. Here the repeated counting is the point, and the constraint of 1000 letters keeps it fast.

    Take s = "ae" and t = "aea". The first letter of t is "a". It appears once in s and twice in t, so the counts differ and the method returns "a". The extra letter is a copy of a letter already in s, and the check still finds it, because it compares counts and not mere presence.

    Step by step

    1. Write the helper countChar(str, ch) first. It returns how many times the one-character string ch appears in str. The main method will call it twice per letter, so it deserves its own name.
    2. Start a counter with let count = 0. It is let because it changes.
    3. Loop over the characters of str with for...of. Looping over a string gives one character at a time as a string.
    4. Compare each character with ch using ===. Two strings are equal when their contents are equal.
    5. Add one to count on every match.
    6. Return count after the loop.
    7. In findTheDifference, loop over t, not s. The answer is a letter of t, and s may be empty.
    8. Compare the two counts of the current letter with this.countChar(s, i) !== this.countChar(t, i). The this. prefix is needed to call another method of the same class.
    9. Return the letter as soon as the counts differ. Exactly one letter can differ, so the first mismatch is the answer.

    The solution in TypeScript

    class Solution {
    countChar(str: string, ch: string): number {
        let count = 0;
        for (const c of str) {
            if (c === ch) {
                count++;
            }
        }
        return count;
    }
    findTheDifference(s: string, t: string): string {
        for (const i of t) {
            if (this.countChar(s, i) !== this.countChar(t, i)) {
                return i;
            }
        }
    }
}

    The TypeScript details worth a closer look:

    • There is no char type. A letter is a string of length 1, which is why countChar takes ch: string and the method returns string.
    • for...of versus for...in. for (const c of str) yields the characters. for...in would yield the indexes as strings, and comparing "0" with a letter never matches.
    • The loop variable is named i, but it holds a letter. That name is just the lesson's choice. It is a letter, so don't use it as an index.
    • The missing final return. The method ends after the loop without returning anything. Because the problem guarantees a mismatch, the loop always returns first. With this lesson's compiler settings, tsc doesn't report the missing return. If an input broke the guarantee, the method would return undefined although its declared type says string, since types are erased when the code compiles to JavaScript and nothing checks the result at run time.
    • Methods need this. Writing countChar(s, i) without this. refers to a function that doesn't exist outside the class.

    Complexity

    Time: O(n²). Each countChar call walks one string, which is at most n characters. The main loop makes two calls for each of the up to n letters of t. It stops early at the first mismatch, but the extra letter can be at the end of t, and the worst case is the full n iterations.

    Space: O(1). The method keeps a counter and a loop variable and builds no table.

    Edge cases and common mistakes

    • Empty s. With s = "" and t = "y", countChar("", "y") is 0 and countChar("y", "y") is 1, so the method returns "y".
    • The extra letter repeats a letter of s. For s = "a" and t = "aa", the counts are 1 and 2, so the answer is "a". A check that only asks whether s contains the letter would miss this.
    • Looping over s instead of t. The extra letter may not appear in s at all, as with "y" above, so a loop over s would never meet it. For s = "" the loop would not run.
    • Counting only t. A letter that appears twice in t is not necessarily the extra one. Only the comparison with s tells.

    Testing

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