LESSON 306 OF 677 · BRUTE FORCE

Find the Difference

Practice O(n²)

You get two strings, s and t. To make t, someone shuffled s and added one extra letter.

Return the extra letter as a Char.

Example 1:

Input: s = "plan", t = "nlapk"
Output: k
Explanation: t is "plan" shuffled, plus a 'k'.

Example 2:

Input: s = "moon", t = "noomo"
Output: o
Explanation: s has two o's.
t has three o's.
The extra letter is an 'o'.

Example 3:

Input: s = "", t = "w"
Output: w

Constraints:

s has 0 to 1,000 letters.
t has exactly one more letter than s.
Both strings use only 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(s: String, c: Char): Int that loops through s and tallies matches. Then:

for (i in t) {
    if (countChar(s, i) != 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