Skip to main content

389. Find the Difference

easy

String t is a shuffled copy of string s with one extra character inserted. Find that extra character — in linear time using either XOR-on-codepoints or character-sum subtraction.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

Constraints

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s and t consist of lowercase English letters.

Examples

Example 1

Input
s = "abcd", t = "abcde"
Output
"e"

Explanation: 'e' is the letter that was added.

Example 2

Input
s = "", t = "y"
Output
"y"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash-map letter counts of s and t and find the off-by-one character — O(n) time, O(1) space (26 letters).

Hint 2

Or sum the character codepoints of t and subtract the sum from s. The difference is the extra letter's codepoint.

Hint 3

XOR variant: XOR every codepoint of s and t together. Paired letters cancel; the extra one survives.

Solution approach

Reveal approach

XOR cancellation. Initialize result = 0. XOR the codepoint of every character in both s and t into result. Because each character that appears in both strings shows up twice, those bits cancel. Only the extra character in t survives — return chr(result). O(n) time, O(1) space. The codepoint-sum variant works too (sum(t) - sum(s) = extra codepoint) but is slightly less safe in fixed-width languages where overflow could matter for adversarial inputs; here both strings are bounded by 1000 so either works.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • xor

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Find the Difference and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →