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.

Bit manipulation 1 0 1 1 0 1 0 XOR pairs · masks · shifts

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

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;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

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

How the code works:

  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

Walkthrough — input s = "abcd", t = "abcde", expected output 'e':

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    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

References

Template Reference