You are given two strings s and t. String t is generated by randomly shuffling s and then adding one more letter at a random position. Return the letter that was added.

Examples

Example 1:

Input: s = "abcd", t = "abcde"
Output: 'e'

Example 2:

Input: s = "", t = "y"
Output: 'y'

Constraints

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s and t consist of lowercase English letters

Thinking Process

Every character in s appears in t, plus one extra. We need to find that extra character. Three approaches:

  1. Frequency counting: count characters in both strings, find the mismatch
  2. Sum difference: sum all ASCII values in t, subtract sum of s – the remainder is the added character
  3. XOR: XOR all characters in both strings – pairs cancel out, leaving only the added character

XOR is the cleanest: a ^ a = 0 and 0 ^ a = a, so every matched pair cancels.

Solution 1: XOR – $O(n)$ time, $O(1)$ space

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

Time: $O(n)$ Space: $O(1)$

Solution 2: Sum Difference – $O(n)$ time, $O(1)$ space

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

Time: $O(n)$ Space: $O(1)$

Solution 3: Frequency Count – $O(n)$ time, $O(1)$ space

class Solution {
public:
    char findTheDifference(string s, string t) {
        int freq[26] = {};
        for (char ch : s) freq[ch - 'a']++;
        for (char ch : t) freq[ch - 'a']--;
        for (int i = 0; i < 26; i++) {
            if (freq[i] < 0) return 'a' + i;
        }
        return 0;
    }
};

Time: $O(n)$ Space: $O(1)$ (fixed 26-element array)

Comparison

Approach Time Space Notes
XOR $O(n)$ $O(1)$ Cleanest, no overflow risk
Sum $O(n)$ $O(1)$ Simple, slight overflow risk for very long strings
Frequency $O(n)$ $O(1)$ Most explicit, works for any “find extra” variant

Common Mistakes

  • Using XOR but forgetting to initialize to 0
  • Sum approach: using char instead of int for the accumulator (overflow for long strings)

Key Takeaways

  • “Find the single extra/missing element” = XOR is the go-to bit trick
  • Same XOR pattern appears in LC 136 (Single Number) – any problem where elements pair up except one
  • All three approaches are $O(n)$ time, $O(1)$ space, but XOR is the most elegant

Template Reference