Code Implementation

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        # Using XOR to find the extra character
        result = 0
        for ch in s:
            result ^= ord(ch)
        for ch in t:
            result ^= ord(ch)
        return chr(result)
      

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

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

var findTheDifference = function(s, t) {
    let result = 0;
    for (let ch of s) {
        result ^= ch.charCodeAt(0);
    }
    for (let ch of t) {
        result ^= ch.charCodeAt(0);
    }
    return String.fromCharCode(result);
};
      

Problem Description

You are given two strings, s and t. String t is generated by shuffling string s and then adding one extra character at a random position. Your task is to find and return the extra character that was added to t.

• Both s and t consist of lowercase English letters.
• You can assume there is exactly one extra character in t that is not in s.
• Do not reuse elements; each character in s can only match one character in t.

Thought Process

At first glance, the problem seems to require comparing each character in t with those in s and finding which one is extra. A brute-force approach would involve checking each character of t against s and removing matches, but that would be inefficient for longer strings.

To optimize, we recognize that since t is just s with one extra character, their combined character counts will differ by exactly one for the added character. This insight suggests using counting techniques or mathematical operations to efficiently spot the difference.

Another clever approach is to use the XOR operation, since XOR-ing two identical numbers cancels them out (resulting in zero), and XOR is commutative and associative. If we XOR all characters in both strings, all matching pairs will cancel out, leaving only the extra character from t.

Solution Approach

• Step 1: Initialize a variable (e.g., result) to zero.
• Step 2: Iterate over each character in s and XOR its ASCII (or Unicode) value with result.
• Step 3: Do the same for each character in t.
• Step 4: After processing both strings, all identical characters will have canceled out due to the properties of XOR, leaving only the ASCII value of the extra character.
• Step 5: Convert the final result back to a character and return it.

This approach is both time and space efficient. We use a variable to accumulate the XOR, and the runtime is linear in the length of the strings.

Why XOR? Since a ^ a = 0 and 0 ^ b = b, all matching characters in s and t will cancel out, and only the extra character remains.

Example Walkthrough

Let's walk through an example with s = "abcd" and t = "abcde".

1. Initialize result = 0.
2. Process each character in s:
   • result ^= ord('a') → result becomes 97
   • result ^= ord('b') → result becomes 3
   • result ^= ord('c') → result becomes 96
   • result ^= ord('d') → result becomes 4
3. Process each character in t:
   • result ^= ord('a') → result becomes 101
   • result ^= ord('b') → result becomes 7
   • result ^= ord('c') → result becomes 100
   • result ^= ord('d') → result becomes 0
   • result ^= ord('e') → result becomes 101
4. The final result is 101, which corresponds to the character 'e'.

Thus, the function returns 'e', which is the extra character in t.

Time and Space Complexity

• Brute-force approach:
  For each character in t, check if it exists in s and remove it if found. This results in O(n^2) time complexity, where n is the length of the strings, due to repeated searches and removals.
• Optimized XOR approach:
  We iterate through both strings once, so the time complexity is O(n). The space complexity is O(1), since we only use a single variable for accumulation.
• Alternative (counting with hash map):
  Also O(n) time and O(1) space (since there are only 26 lowercase letters).

The XOR method is optimal in both time and space.

Summary

To solve the "Find the Difference" problem, we leverage the properties of the XOR operation to efficiently detect the extra character added to string t. This method is both simple and elegant: by XOR-ing all characters in both strings, all matching pairs cancel out, leaving only the extra character. This approach is optimal, with linear time and constant space complexity, and is easy to implement across multiple programming languages.