Skip to content
← All posts

Find the Difference: XOR to Spot the Extra Character

3 min read
leetcodeproblemeasystringshash-mapbit-manipulation

Find the Difference is LeetCode 389, rated Easy. You are given two strings s and t. String t is generated by randomly shuffling s and then adding one extra character at a random position. Your job is to find that added character.

For example, if s = "abcd" and t = "abcde", the answer is 'e' because it is the only character in t that was not in s.

You could count character frequencies with a hash map, but there is a cleaner way. XOR gives you the answer in one pass with no extra data structures.

The key insight

XOR has a cancellation property: when you XOR a value with itself, the result is 0. And XOR-ing anything with 0 gives back the original value. If you XOR every character from both s and t together, every character that appears in both strings cancels out. The only character left is the one that was added.

This works because t contains exactly the same characters as s plus one extra. Every character from s has a matching partner in t, and those pairs cancel to 0. The extra character has no partner, so it survives.

s = "abcd"a[0]b[1]c[2]d[3]t = "abcde"a[0]b[1]c[2]d[3]e[4]extra characterXOR all chars from s and t = 'e'
String t has one extra character compared to s. XOR all characters from both strings and the extra one survives.

The approach

  1. Initialize result = 0
  2. XOR every character in s into result
  3. XOR every character in t into result
  4. Convert result back to a character

After step 3, every shared character has been XOR-ed exactly twice (once from s, once from t), cancelling to 0. The added character has been XOR-ed exactly once, so it is all that remains.

The code

def find_the_difference(s: str, t: str) -> str:
    result = 0
    for ch in s:
        result ^= ord(ch)
    for ch in t:
        result ^= ord(ch)
    return chr(result)
Practice this pattern

Step 1: Initialize result = 0

Start with a result of 0. XOR with 0 preserves any value, so this is the neutral starting point.

result = 0

Step 2: XOR every character in s

Walk through s = "abcd" and XOR each character's ordinal value into result. After this loop, result holds a ^ b ^ c ^ d.

result = 0 ^ 97 ^ 98 ^ 99 ^ 100 (= 96 in decimal)

Step 3: XOR every character in t

Now walk through t = "abcde" and XOR each character into result. The a, b, c, d characters appear in both strings, so they cancel out pairwise.

result = 96 ^ 97 ^ 98 ^ 99 ^ 100 ^ 101

Step 4: Pairs cancel, extra survives

Each character shared between s and t has been XOR-ed twice, which cancels to 0. Only the extra character 'e' (ordinal 101) survives.

result = 101 → chr(101) = 'e'
Drill this from memory

Complexity

TimeSpace
TotalO(n)O(1)

Time: O(n). You iterate through both strings once. String s has length n and t has length n + 1, so the total work is 2n + 1 operations, which is O(n).

Space: O(1). You only use a single integer variable result. No hash maps, no arrays, no extra storage that grows with input size.

Building blocks

XOR cancellation

XOR cancellation is the same technique used in Single Number. The core idea: when you XOR a collection of values and every value appears an even number of times except one, that one value is the result. Here, each shared character appears twice (once in s, once in t), so it cancels. The added character appears once, so it survives.

This pattern shows up whenever you need to find an unpaired element. Recognize the signal: two collections that are almost identical, differing by exactly one element.

Edge cases

  • Single character. If s is empty and t has one character, the loop over s does nothing and the loop over t XORs that single character with 0. The result is the added character itself. 0 ^ x = x handles this cleanly.
  • Added character is the same as an existing one. If s = "aa" and t = "aaa", the three a values XOR together: a ^ a ^ a ^ a ^ a = a. Two from s and three from t give five total XOR operations. Four cancel in pairs, leaving one a. The algorithm does not care whether the added character is new or a duplicate.

From understanding to recall

You have seen XOR cancellation before if you solved Single Number or Missing Number. The pattern is always the same: initialize to 0, XOR everything in, and the unpaired value falls out. What changes between problems is how you frame the two "collections" that overlap.

For Find the Difference, the two collections are the characters of s and the characters of t. For Single Number, it is the array elements paired against themselves. For Missing Number, it is array values paired against their indices. The underlying mechanic is identical.

Drill the XOR accumulation loop a few times from scratch. Once the pattern is automatic, you will recognize it instantly whenever a problem asks you to find the one element that does not have a match.

Try CodeBricks free

Related posts