String t is string s shuffled with one extra letter added. Find that letter.
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 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)
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.
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.