Start learning free

LESSON 218 OF 438 · BRUTE FORCE

Find the Difference in JavaScript: Brute Force Counting

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.

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.

JavaScript doesn't have a built-in count method, so we'll write a small helper countChar(str, ch) 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(n²) 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

Guided

Ctrl + Enter to check

JAVASCRIPT · BRUTE FORCE

Find The Difference in JavaScript, explained

Problem overview

The method findTheDifference(s, t) receives two strings of lowercase letters. The string t contains every letter of s, shuffled, plus exactly one extra letter somewhere. The method returns that extra letter as a one-character string.

With s = "abcd" and t = "abcde", every letter of s appears once in t, and e has no partner, so the answer is "e". With s = "" and t = "y" there is nothing to pair with, so the answer is "y". The string s can be empty, and t is always exactly one character longer.

Approach: compare counts, letter by letter

The extra letter has to be one of the letters in t, so the search can walk through t and test each letter: "is this the extra one?"

A letter is the extra one exactly when it appears more often in t than in s. Every other letter appears the same number of times in both strings, because t is a shuffle of s plus one more letter. So for each letter of t, count it in s, count it in t, and compare. The first letter whose two counts differ is the answer.

Take s = "aab" and t = "abaa". The letter a appears 2 times in s and 3 times in t, so the very first letter of t already gives the answer "a". With t = "bab" and s = "ab", the letter b is counted 1 time in s and 2 times in t, and the method returns "b".

This is the simplest correct idea, and it is slow: counting a letter walks a whole string, and the method does it for every letter of t. That makes it O(n²). The next lessons on this problem keep the counts in a hash table and then use XOR to reach O(n). This one starts from the version that is easiest to get right.

Step by step

Write a helper called countChar(str, ch) on the Solution class, above findTheDifference. It answers one question, "how many times does ch appear in str?", and the main method asks it twice per letter.
Declare count with let and set it to 0. It is the running tally, and it changes, so it can't be a const.
Loop over str with for...of. Looping over a string with for...of gives one character at a time, and const c is fine because each pass creates a fresh variable.
Check c === ch. Both are one-character strings, and === compares them without any type conversion.
Increment count inside the if block.
Return count after the loop, so the helper reports the total only once every character has been checked.
In findTheDifference, loop over t. The extra letter is guaranteed to be in t, so there is no reason to look at the letters of s.
Compare the two counts. Inside a class, the helper is called with this.countChar(...). A mismatch means this letter appears more often in t than in s.
Return the letter at once. Exactly one letter has mismatched counts, so there is nothing left to look for.

The solution in JavaScript

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

Some JavaScript details worth a closer look:

Methods need this.. countChar is a method of the class, not a free function. Writing countChar(s, i) without this. looks for a variable of that name and throws a ReferenceError.
for...of versus for...in. for (const c of str) yields the characters. for (const c in str) would yield the indexes, as strings, and the comparison c === ch would never be true.
No return at the end. A function that finishes without reaching a return gives back undefined. Here that can't happen for valid input, because one letter always differs, but it is why the method has no final line.
Strings are compared by value. "a" === "a" is true, so the helper's c === ch works for strings with no extra care.

Complexity

Time: O(n²), where n is the length of t. The outer loop visits up to n letters, and for each one countChar walks s and then t, about 2n steps. That is roughly 2n² steps in the worst case, which is O(n²). With the lesson's limit of 1000 letters, this is a few million steps at most, which is fast enough.

Space: O(1). The method keeps a counter and a loop variable, and never builds a new string or array.

Edge cases and common mistakes

An 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 is a repeat. With s = "aab" and t = "abaa", the answer is "a", a letter that is already in s. Checking only "is this letter missing from s?" would find nothing, which is why the lesson compares counts.
Looping over s instead of t. If the extra letter is new, it never shows up in the loop, and the method returns undefined.
Comparing with == or the wrong operator. The check is !== between two numbers. Writing = by mistake assigns instead of comparing.
Counting only in one string. The comparison needs both counts. A letter that appears twice in s and twice in t is not the extra one.

Testing

s = "abcd", t = "abcde" gives "e".
s = "", t = "y" gives "y".
s = "aab", t = "abaa" gives "a".
s = "ab", t = "bab" gives "b".

Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free