String t is string s shuffled, with one extra letter added at a random position. Return the added letter.
DSA Animator › DSA Revision › Bit Manipulation › Find the Difference
Remember: XOR finds the odd one out, even with characters. The sum of codes of t minus the sum of s works as well. The video solves Find the Difference (LeetCode 389, Easy) with the XOR on Characters pattern from the Bit Manipulation topic, and you can replay every step in the interactive Find the Difference animation.
String t is string s shuffled, with one extra letter added at a random position. Return the added letter.
For s equal to abcd and t equal to abcde, the answer is e.
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 the a from s with the a from t, and they cancel. The same happens for b, c and d. The only character with no partner is e. So the result is the character code of e. The answer is e.
In code, start with a char variable set to 0. XOR every character of s, and every character of t. Return the result as a char, so it's O of n time and O of 1 space.
Remember: XOR finds the odd one out, even with characters. The sum of codes of t minus the sum of s works as well.