Find the Difference

The Find the Difference problem appears frequently in coding interviews and warm-up exercises because it tests your understanding of character frequency, hashing, and bitwise reasoning. At first glance, it looks like a simple string comparison task. But the trick lies in choosing an approach that is both elegant and efficient, especially when dealing with large strings or limited memory scenarios.

This problem reinforces a key interview skill: recognizing when counting, hashing, or bitwise XOR can eliminate unnecessary work.

Problem

You are given two strings, \( s \) and \( t \). String t is created by shuffling the characters of string s and then adding one additional character somewhere in the string.

Your task:

Return the extra character that appears in t but not in s.

You are guaranteed:

• \( t \) is exactly one character longer than \( s \)
• All characters are lowercase English letters
• The order of characters is irrelevant to determining the result

Example

Input:

s = “abcd”

t = “abcde”

Output:

"e"

Explanation:

String t contains all the original characters of \( s \), plus an extra \( e \).

Another example:

s = ""

t = “y”

Output:

"y"

Even in this degenerate case, the idea remains the same: identify the character that only appears in \( t \).

Solution

You could approach this problem in multiple ways—hash maps, sorting, or frequency arrays—but the most optimal and elegant solution uses a bitwise trick.

Key idea

If you XOR (^) all characters of both strings (s and t), every character that appears in both strings cancels out because:

x ^ x = 0

And:

0 ^ y = y

Since all characters in s appear in t except one new character, the XOR of all characters from both strings leaves only the extra character.

Why XOR works

• XOR is commutative and associative, so order doesn’t matter.
• Pairs of identical characters cancel out.
• You end with exactly the character that doesn’t have a matching pair.

This takes:

• \( O(n) \) time
• \( O(1) \) extra space

No frequency tables, no sorting, no hashing—just a single pass over the data.

Algorithm outline

1. Initialize a variable result = 0.
2. For each character in \( s \), XOR it with result.
3. For each character in \( t \), XOR it with result.
4. After processing all characters, the value stored in result will be the ASCII code of the extra character.
5. Convert it back to a character and return it.

Sample implementation (Python)

Alternative solution: counting frequencies

You can also track character counts with an array of size 26. Compare the frequencies and return the character with a mismatch.

This is straightforward and intuitive but requires more memory than the XOR approach.

Alternative solution: sorting

Sort both strings and compare them character by character.
This works but costs \( O(n log n) \) time due to sorting.

Interview insight

The Find the Difference problem is one of those questions where the brute-force solution is obvious, but the optimal solution is subtle and elegant. Interviewers often use it to see whether you:

• Recognize opportunities for XOR-based simplification
• Understand character frequency techniques
• Can articulate why your approach is optimal

Once you master this, you’ll recognize XOR patterns in numerous other problems involving pairs, missing elements, or parity checks.