Find the Difference

How it works

XOR has a useful property: a ^ a = 0 and a ^ 0 = a. If we XOR all characters from both strings together, each character that appears in both s and t will cancel out (XOR with itself gives 0). The only character remaining is the added one, since it appears an odd number of times total.

Steps

1. Initialize res = 0.
2. XOR res with each character's ASCII value in s.
3. XOR res with each character's ASCII value in t.
4. Convert res to a character and return it.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting to Handle Empty String s

When s is an empty string, t contains exactly one character (the added one). Solutions that iterate through s first or rely on finding a mismatch between sorted strings must handle this edge case. The XOR and sum-based approaches naturally handle this since XORing or summing over an empty string contributes nothing.

Comparing Characters Instead of Counts

A common mistake is to iterate through both strings and return the first character in t that does not appear in s. This fails when the added character is a duplicate of an existing character. For example, if s = "a" and t = "aa", the added character is 'a', but a naive check would miss it since 'a' already exists in s.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for c in s:
            res ^= ord(c)
        for c in t:
            res ^= ord(c)
        return chr(res)

class Solution {
public:
    char findTheDifference(string s, string t) {
        int res = 0;
        for (char c : s) {
            res ^= c;
        }
        for (char c : t) {
            res ^= c;
        }
        return (char) (res);
    }
};