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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →