Find the Difference — DSA Visualizer

Find the Difference LC #389 Easy XOR All Chars

Problem

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

Example 1

Input: s = "abcd", t = "abcde"

Output: "e"

Explanation: "e" is the added letter.

Example 2

Input: s = "", t = "y"

Output: "y"

Explanation: "y" is the added letter.

Constraints: 0 ≤ s.length ≤ 1000 | t.length == s.length + 1 | lowercase English letters

Try Examples

Custom:

Character Tiles — XOR Walkthrough

XOR Accumulator (c)

c = 0 (code: 0)

Variables

c (char)

—

c (code)

src

—

Step Logic

Press ▶ Play or Next Step to begin.

Ready

0 / 0

Select an example above and press Play.

Algorithm

XOR all characters in s

XOR all characters in t

Matching chars cancel out (x^x=0)

Remaining value is the added character

Time

O(n)

Space

O(1)

Why It Works

XOR is commutative and associative. x ^ x = 0, x ^ 0 = x. XOR-ing all chars of both strings leaves only the extra char since all others appear twice and cancel. Order does not matter — even though t is a shuffled version of s with one extra char, XOR-ing everything together causes every paired character to self-cancel, leaving only the lone extra character.