Find the Difference (LeetCode 389): Counting vs XOR

String t is string s shuffled with one extra letter added. Find that letter.

Counting

from collections import Counter

def find_the_difference(s: str, t: str) -> str:
    return next(iter(Counter(t) - Counter(s)))

O(n) time, O(1) space since the alphabet is 26 letters.

XOR trick

XOR every character code in both strings. Pairs cancel, leaving the extra character:

def find_the_difference(s: str, t: str) -> str:
    x = 0
    for c in s + t:
        x ^= ord(c)
    return chr(x)

Sum trick

chr(sum(map(ord, t)) - sum(map(ord, s))) also works and is easy to explain. In languages with fixed-width integers, XOR avoids any overflow worry.

Which to give

Lead with counting because it generalizes (several extra letters), then offer XOR as the constant-space flourish. Interviewers like hearing the trade-off. You can rehearse explaining trade-offs like this with interview copilot app.

Disclosure: I work on Linkjob AI.