LESSON 302 OF 673 · 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 character.

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.

Python strings have a built-in count() method. s.count(i) returns how many times i appears in s. So we can write:

for i in t:
    if s.count(i) != t.count(i):
        return i

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

Guided

Ctrl + Enter to check