LESSON 308 OF 679 · 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 count_char(s: &str, c: char) -> i32 that loops through s.chars() and tallies matches. Then:

for i in t.chars() {
    if Self::count_char(s, i) != Self::count_char(t, i) {
        return i;
    }
}

This brute-force approach is O(n²) because each count_char 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