Bit Manipulation - Find the Difference

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.

Input: s = "abcd", t = "abcde"
Output: 'e'
Explanation: 'e' is the letter added to t.

Input: s = "", t = "y"
Output: 'y'
Explanation: 'y' is the only character and is the added one.

XOR all characters in both s and t together. Characters that appear in both strings cancel out (c ^ c = 0), leaving only the extra character added to t.

Initialize result = 0.
XOR every character in s into result.
XOR every character in t into result.
The remaining value is the added character.

class Solution { public char findTheDifference(String s, String t) { char result = 0; for (char c : s.toCharArray()) result ^= c; for (char c : t.toCharArray()) result ^= c; return result; } }

Complexity Analysis:

Time complexity: O(n) — one pass through each string.
Space complexity: O(1) — constant extra space.