You are given two strings s and t. String t is generated by random shuffling string s and then adding one more letter at a random position. Return the letter that was added to t.
s = "abcd", t = "abcde""e"s = "", t = "y""y"XOR is commutative and associative. x ^ x = 0, x ^ 0 = x. XOR-ing all chars of both strings leaves only the extra char since all others appear twice and cancel. Order does not matter — even though t is a shuffled version of s with one extra char, XOR-ing everything together causes every paired character to self-cancel, leaving only the lone extra character.
Counting letters with an array of 26 works. Sorting both strings and comparing also works, but it is slower.
Characters are just numbers, so XOR works on them too. Every letter of s also appears in t, so each one appears twice in total. XOR all characters of both strings, and every pair cancels. The only character left is the extra one.
XOR finds the odd one out, even with characters. The sum of codes of t minus the sum of s works as well.
Run the animation above on your own input, or watch the 1:21 video explanation of Find the Difference with a dry run and Java code.