Find the Difference
XOR all characters of both strings — the lone unmatched char survives.
2 min read
bit-manipulation xor string
Problem#
t is s shuffled with one extra random letter added. Return the added letter.
Examples#
s="abcd", t="abcde"→'e'.s="", t="y"→'y'.
Constraints#
0 <= s.length <= 1000,t.length = s.length + 1, lowercase only.
Approach#
XOR every character of s and t together. Pairs cancel, leaving the lone added char.
Solution#
class Solution {public: char findTheDifference(string s, string t) { char x = 0; for (char c : s) x ^= c; for (char c : t) x ^= c; return x; }};func findTheDifference(s string, t string) byte { var x byte = 0 for i := 0; i < len(s); i++ { x ^= s[i] } for i := 0; i < len(t); i++ { x ^= t[i] } return x}class Solution: def findTheDifference(self, s: str, t: str) -> str: x = 0 for c in s: x ^= ord(c) for c in t: x ^= ord(c) return chr(x)var findTheDifference = function(s, t) { let x = 0; for (let i = 0; i < s.length; i++) x ^= s.charCodeAt(i); for (let i = 0; i < t.length; i++) x ^= t.charCodeAt(i); return String.fromCharCode(x);};class Solution { public char findTheDifference(String s, String t) { char x = 0; for (int i = 0; i < s.length(); i++) x ^= s.charAt(i); for (int i = 0; i < t.length(); i++) x ^= t.charAt(i); return x; }}function findTheDifference(s: string, t: string): string { let x = 0; for (let i = 0; i < s.length; i++) x ^= s.charCodeAt(i); for (let i = 0; i < t.length; i++) x ^= t.charCodeAt(i); return String.fromCharCode(x);}Editorial#
XOR’s self-inverse property turns “find the unmatched” into a one-pass fold. Equivalent to summing/subtracting char codes but cleaner because it avoids overflow concerns and works for any character set.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#