Start learning free

LESSON 591 OF 677 · BIT MANIPULATION

Find the Difference

Practice O(n) / O(1)

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 and use O(1) extra space, where n is the length of t.



Every letter has a code number. XOR on two numbers has two useful properties: x XOR x = 0 and x XOR 0 = x, and the order of the numbers doesn't matter.

Start from 0 and XOR in the code of every letter of s and of every letter of t. Each letter of s has an equal partner in t, so the pairs cancel out. What is left is the code of the extra letter: turn it back into a Char.

We walk through s once and t once, one XOR per letter: O(n) time.
We keep a single number, so the extra space is O(1).
STEP 1 OF 6
    Ctrl + Enter to check