---

1. Problem Summary

You are given two strings:

• s — the original string
• t — the same string as s but with one extra character added and shuffled

Your task is to identify and return the extra character that appears in t but not in s.

Important characteristics:

• Strings consist of lowercase English letters.
• Exactly one additional character exists in t.
• Characters may repeat, but only one extra occurrence overall is guaranteed.

Example interpretation:
If s = "abcd" and t = "abcde", the answer is 'e'.

---

2. Key Insights

Counting characters works but is unnecessary

You could count occurrences of each letter, but there is a simpler method.

XOR property provides elegant solution

Key properties of XOR:

1. a ^ a = 0
2. a ^ 0 = a
3. XOR is commutative and associative

Therefore:

s1 ^ s2 ^ ... ^ sn ^ t1 ^ t2 ^ ... ^ t(n+1) = extraChar

Matching characters cancel each other out, leaving only the extra character.

No sorting or data structures required

XOR solution uses constant memory.

Works even with repeated characters

Since duplicates cancel out pairwise, only the odd-occurring one survives.

---

3. Approach

XOR-based solution

Steps:

1. Initialize a variable result = 0
2. XOR each character in string s with result
3. XOR each character in string t with result
4. Remaining value in result is the extra character

This works because identical characters nullify each other in XOR.

---

4. Time and Space Complexity

Time Complexity: O(N)

Where N = length of string t. All characters scanned once.

Space Complexity: O(1)

Only one variable maintained.

---

5. Java Solution (XOR Method)

class Solution {
    public char findTheDifference(String s, String t) {
        int result = 0;

        for (char c : s.toCharArray()) {
            result ^= c;
        }

        for (char c : t.toCharArray()) {
            result ^= c;
        }

        return (char) result;
    }
}

---

6. Dry Run Examples

Example 1

Input:

s = "abcd"
t = "abcde"

Step-by-step XOR accumulation:

Start result = 0

Process s:
result ^= ‘a’ → result = ‘a’
result ^= ‘b’ → cancels partially
result ^= ‘c’
result ^= ‘d’

Process t:
result ^= ‘a’ → cancels ‘a’
result ^= ‘b’
result ^= ‘c’
result ^= ‘d’
result ^= ‘e’ → remains 'e'

Final output:

'e'

---

Example 2

Input:

s = "aabbc"
t = "ababbc"

Extra letter is 'b'

XOR cancels all pairs, leaving 'b'

---

Example 3

Input:

s = ""
t = "y"

Only one character:

result = ‘y’

Output:

'y'

---

7. Alternative Approach (Frequency Counting)

class Solution {
    public char findTheDifference(String s, String t) {
        int[] freq = new int[26];

        for (char c : s.toCharArray()) {
            freq++;
        }

        for (char c : t.toCharArray()) {
            freq--;
            if (freq < 0) {
                return c;
            }
        }

        return ' ';
    }
}

When to use this version:

• when character set expands beyond ASCII lowercase
• when interviewer emphasizes counting logic

---

8. Why the XOR Solution Works

• identical characters negate each other
• exactly one character remains unmatched
• XOR compares purely by bit representation
• no ordering or indexing assumptions
• simplest possible memory footprint

---

9. Common Mistakes

1. Sorting both strings (O(N log N) unnecessary)
2. Using HashMap when not required
3. Forgetting t is always exactly one longer
4. Assuming characters must be unique
5. Misinterpreting uppercase or Unicode cases