Start learning free

LESSON 361 OF 667 · HASH TABLE

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.
Note:

For this lesson, your algorithm should run in O(n) time, where n is the length of t.



The brute force counts each letter of t in s again and again. Count the letters of s only once, and keep the counts.

Store the counts in an unordered_map from each letter to how many times it appears in s. Then walk through t: each letter uses up one copy from the unordered_map. The first letter of t that has no copy left (its count is 0, or it was never there) is the extra one.

We walk through s once and t once, and each lookup in the unordered_map is O(1) on average: O(n) time.
The unordered_map never holds more than 26 letters, so the extra space is O(1).
STEP 1 OF 8
    Ctrl + Enter to check