Problem editorial

Find the Difference

EasyBit Manipulation PatternsHash TableStringBit Manipulation

Editorial

Core insight

Find the Difference · Bit Manipulation Patterns

Core Insight for Find the Difference

The move from a sorting or hash map approach to Bit Manipulation relies on the specific properties of the XOR (Exclusive OR) operation, denoted by ^ or $\oplus$ .

The key properties of XOR are:

Self-Inverse: $A \oplus A = 0$ . (XORing a number with itself results in zero).
Identity: $A \oplus 0 = A$ . (XORing a number with zero leaves it unchanged).
Commutative and Associative: The order in which we XOR numbers does not matter. $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ .

Intuition: If we treat the characters as integer ASCII values, we can XOR every character in s and every character in t into a single accumulator variable.

Because t contains all characters of s plus one extra, every character from s will be XORed twice (once from s, once from t). According to the Self-Inverse property, these pairs will cancel each other out to 0. The only value that will remain in the accumulator is the ASCII value of the added character, as it was XORed only once.

Visual Description: Imagine a stream of bits flowing into a logic gate. When the character 'a' from s enters, it flips certain bits. When the matching 'a' from t enters later, it flips those exact same bits back to their original state. The system is stateful; it remembers the "parity" of the bits seen so far. After processing both strings entirely, the final state of the bits represents the binary code of the only character that did not trigger a second flip.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 389: Find the Difference Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes the XOR bitwise operation to cancel out identical characters appearing in both strings, leaving only the added character remaining.

In the LeetCode 389 problem "Find the Difference," we are provided with two strings, s and t. The string t is constructed by shuffling s and appending exactly one new letter at a random position. Our objective is to identify this specific added character. While this may seem like a simple frequency counting problem, it serves as a classic introduction to bit manipulation techniques used in serious technical interviews.

Brute Force Approach for Find the Difference

A common initial approach to solving this problem involves sorting. Since t is a permutation of s with one extra element, sorting both strings aligns the identical characters.

Sort string s alphabetically.
Sort string t alphabetically.
Iterate through the length of s. Compare the character at s[i] with t[i].
The first index where the characters differ indicates that t[i] is the added character.
If the loop completes without finding a difference, the added character must be the last character of t.

Pseudo-code:

text

function findDifference(s, t):
    sort(s)
    sort(t)
    for i from 0 to length(s) - 1:
        if s[i] != t[i]:
            return t[i]
    return t[last_index]

Time Complexity Analysis: The time complexity is dominated by the sorting operation, which is $O(N \log N)$ , where $N$ is the length of the string.

Why it is suboptimal: While $O(N \log N)$ is acceptable for small constraints ( $N \le 1000$ ), it is inefficient compared to linear time solutions. Sorting destroys the original order to establish a comparison, but we do not actually need the data to be ordered—we only need to determine identity. We can solve this in $O(N)$ without the overhead of sorting algorithms.

Algorithm Strategy: Bit Manipulation Patterns

The strategy is to maintain a single running variable, often initialized to 0 (or the first element, depending on implementation preference). We iterate through both strings, applying the XOR operation between the running variable and the ASCII value of the current character.

Initialization: Create a variable (e.g., result) initialized to 0. This acts as our accumulator.
Process String s: Loop through each character in s, converting it to its integer representation, and update result using result ^= char_code.
Process String t: Loop through each character in t, doing the same.
Final State: Due to the cancellation property, result now holds the integer value of the unique character.
Output: Convert result back to a character and return it.

This approach requires no auxiliary data structures like Hash Maps or Arrays, strictly adhering to $O(1)$ space complexity.

Execution Flow

Let's trace the algorithm with s = "ab", t = "cba".

Initialize: result = 0 (Binary 00000000).
Process s ("ab"):
- Current char: 'a' (ASCII 97). result = 0 ^ 97 = 97.
- Current char: 'b' (ASCII 98). result = 97 ^ 98.
Process t ("cba"):
- Current char: 'c' (ASCII 99). result = 97 ^ 98 ^ 99.
- Current char: 'b' (ASCII 98). result = 97 ^ 98 ^ 99 ^ 98.
- Current char: 'a' (ASCII 97). result = 97 ^ 98 ^ 99 ^ 98 ^ 97.
Simplification (Mental Model):
- Rearrange terms (associativity): (97 ^ 97) ^ (98 ^ 98) ^ 99.
- Apply cancellation: 0 ^ 0 ^ 99.
- Apply identity: 99.
Result: The value 99 corresponds to the character 'c'.

Proof of Correctness

The correctness relies on the mathematical definition of the XOR field. Let $C_s$ be the set of characters in s and $C_t$ be the set of characters in t. We calculate: $Result = (\bigoplus_{c \in C_s} c) \oplus (\bigoplus_{c \in C_t} c)$ Since $C_t = C_s \cup \{x\}$ where $x$ is the added character, the equation becomes: $Result = (\bigoplus_{c \in C_s} c) \oplus (\bigoplus_{c \in C_s} c) \oplus x$ $Result = ((\bigoplus_{c \in C_s} c) \oplus (\bigoplus_{c \in C_s} c)) \oplus x$ $Result = 0 \oplus x = x$ Thus, the algorithm is mathematically guaranteed to return the added character.

Pattern Reuse Notes

The Bitwise XOR - Finding Single/Missing Number pattern is highly reusable. Understanding the cancellation property applies directly to these problems:

LeetCode 136: Single Number - Identical logic: find the element appearing once in an array of duplicates.
LeetCode 137: Single Number II - A variation where elements appear three times; requires more complex bit logic but follows the same principle.
LeetCode 268: Missing Number - XORing the array indices against the values to find the missing index.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 389

cpp

1class Solution {
2public:
3    char findTheDifference(string s, string t) {
4        char result = 0;
5        
6        // XOR all characters in s
7        for (char c : s) {
8            result ^= c;
9        }
10        
11        // XOR all characters in t
12        // Matching characters will cancel out
13        for (char c : t) {
14            result ^= c;
15        }
16        
17        return result;
18    }
19};

Java Solution for LeetCode 389

java

1class Solution {
2    public char findTheDifference(String s, String t) {
3        char result = 0;
4        
5        // Iterate through s and XOR
6        for (int i = 0; i < s.length(); i++) {
7            result ^= s.charAt(i);
8        }
9        
10        // Iterate through t and XOR
11        for (int i = 0; i < t.length(); i++) {
12            result ^= t.charAt(i);
13        }
14        
15        return result;
16    }
17}

Python Solution for LeetCode 389

python

1class Solution:
2    def findTheDifference(self, s: str, t: str) -> str:
3        result = 0
4        
5        # In Python, we must convert char to int using ord()
6        for char in s:
7            result ^= ord(char)
8            
9        for char in t:
10            result ^= ord(char)
11            
12        # Convert the final integer back to a character
13        return chr(result)

AI Coach Insight

For Find the Difference, focus on explaining why the structure works, not just naming Bit Manipulation Patterns.

Complexity Analysis

Time Complexity: $O(N)$ We iterate through string s of length $N$ and string t of length $N+1$ exactly once. The XOR operation is constant time. Thus, the total time is proportional to $2N + 1$ , which simplifies to linear time $O(N)$ .

Space Complexity: $O(1)$ We use a single integer variable to store the XOR sum. This requires constant extra space regardless of the input string size. This is superior to Hash Map approaches which would require $O(1)$ space relative to $N$ but technically $O(26)$ or $O(128)$ depending on the character set size.

Related Patterns

Pattern: Bit Manipulation Patterns
Subpattern: Bitwise XOR - Finding Single/Missing Number

This problem is a direct application of the XOR cancellation property. We have a set of characters where every character appears exactly twice (once in s, once in t) except for one character which appears exactly once (in t). This structure perfectly fits the "Single Number" subpattern.

Common Mistakes & FAQ

Why does the naive solution often result in Time Limit Exceeded (TLE) or suboptimal performance?
- Mistake: Using nested loops to find the character in t that isn't in s.
- Why: A nested loop approach (checking if t[i] exists in s for every char) runs in $O(N^2)$ .
- Consequence: While $N=1000$ might pass, this demonstrates a lack of algorithmic awareness suitable for larger datasets.
Why not just use a Hash Map or Frequency Array?
- Mistake: Using a HashMap<Character, Integer> to count frequencies.
- Why: While correct and $O(N)$ time, it uses extra memory.
- Consequence: This is a valid solution, but the Bit Manipulation approach is strictly superior in terms of space efficiency ( $O(1)$ registers vs heap allocation).
Can we use arithmetic addition and subtraction instead of XOR?
- Mistake: Summing ASCII values of t and subtracting the sum of s.
- Why: This is a valid logic ( $Sum(t) - Sum(s) = added\_char$ ). However, in languages with fixed-size integers, this risks integer overflow if the strings are extremely long.
- Consequence: XOR never overflows because it doesn't increase the magnitude of the number beyond the maximum bit-width of the character type.

Practise Find the Difference and the problems around it

Find the Difference is a Bit Manipulation Patterns problem, in the Bitwise XOR - Finding Single/Missing Number subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Find the Difference · Bit Manipulation Patterns

Core Insight for Find the Difference

The move from a sorting or hash map approach to Bit Manipulation relies on the specific properties of the XOR (Exclusive OR) operation, denoted by ^ or $\oplus$ .

The key properties of XOR are:

Self-Inverse: $A \oplus A = 0$ . (XORing a number with itself results in zero).
Identity: $A \oplus 0 = A$ . (XORing a number with zero leaves it unchanged).
Commutative and Associative: The order in which we XOR numbers does not matter. $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ .

Intuition: If we treat the characters as integer ASCII values, we can XOR every character in s and every character in t into a single accumulator variable.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 389: Find the Difference Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes the XOR bitwise operation to cancel out identical characters appearing in both strings, leaving only the added character remaining.

Brute Force Approach for Find the Difference

A common initial approach to solving this problem involves sorting. Since t is a permutation of s with one extra element, sorting both strings aligns the identical characters.

Sort string s alphabetically.
Sort string t alphabetically.
Iterate through the length of s. Compare the character at s[i] with t[i].
The first index where the characters differ indicates that t[i] is the added character.
If the loop completes without finding a difference, the added character must be the last character of t.

Pseudo-code:

text

function findDifference(s, t):
    sort(s)
    sort(t)
    for i from 0 to length(s) - 1:
        if s[i] != t[i]:
            return t[i]
    return t[last_index]

Time Complexity Analysis: The time complexity is dominated by the sorting operation, which is $O(N \log N)$ , where $N$ is the length of the string.

Algorithm Strategy: Bit Manipulation Patterns

Initialization: Create a variable (e.g., result) initialized to 0. This acts as our accumulator.
Process String s: Loop through each character in s, converting it to its integer representation, and update result using result ^= char_code.
Process String t: Loop through each character in t, doing the same.
Final State: Due to the cancellation property, result now holds the integer value of the unique character.
Output: Convert result back to a character and return it.

This approach requires no auxiliary data structures like Hash Maps or Arrays, strictly adhering to $O(1)$ space complexity.

Execution Flow

Let's trace the algorithm with s = "ab", t = "cba".

Initialize: result = 0 (Binary 00000000).
Process s ("ab"):
- Current char: 'a' (ASCII 97). result = 0 ^ 97 = 97.
- Current char: 'b' (ASCII 98). result = 97 ^ 98.
Process t ("cba"):
- Current char: 'c' (ASCII 99). result = 97 ^ 98 ^ 99.
- Current char: 'b' (ASCII 98). result = 97 ^ 98 ^ 99 ^ 98.
- Current char: 'a' (ASCII 97). result = 97 ^ 98 ^ 99 ^ 98 ^ 97.
Simplification (Mental Model):
- Rearrange terms (associativity): (97 ^ 97) ^ (98 ^ 98) ^ 99.
- Apply cancellation: 0 ^ 0 ^ 99.
- Apply identity: 99.
Result: The value 99 corresponds to the character 'c'.

Proof of Correctness

Pattern Reuse Notes

The Bitwise XOR - Finding Single/Missing Number pattern is highly reusable. Understanding the cancellation property applies directly to these problems:

LeetCode 136: Single Number - Identical logic: find the element appearing once in an array of duplicates.
LeetCode 137: Single Number II - A variation where elements appear three times; requires more complex bit logic but follows the same principle.
LeetCode 268: Missing Number - XORing the array indices against the values to find the missing index.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 389

cpp

1class Solution {
2public:
3    char findTheDifference(string s, string t) {
4        char result = 0;
5        
6        // XOR all characters in s
7        for (char c : s) {
8            result ^= c;
9        }
10        
11        // XOR all characters in t
12        // Matching characters will cancel out
13        for (char c : t) {
14            result ^= c;
15        }
16        
17        return result;
18    }
19};

Java Solution for LeetCode 389

java

1class Solution {
2    public char findTheDifference(String s, String t) {
3        char result = 0;
4        
5        // Iterate through s and XOR
6        for (int i = 0; i < s.length(); i++) {
7            result ^= s.charAt(i);
8        }
9        
10        // Iterate through t and XOR
11        for (int i = 0; i < t.length(); i++) {
12            result ^= t.charAt(i);
13        }
14        
15        return result;
16    }
17}

Python Solution for LeetCode 389

python

1class Solution:
2    def findTheDifference(self, s: str, t: str) -> str:
3        result = 0
4        
5        # In Python, we must convert char to int using ord()
6        for char in s:
7            result ^= ord(char)
8            
9        for char in t:
10            result ^= ord(char)
11            
12        # Convert the final integer back to a character
13        return chr(result)

Find the Difference

Core insight

Core Insight for Find the Difference

Full breakdown

LeetCode 389: Find the Difference Solution & Explanation

Problem Overview

Brute Force Approach for Find the Difference

Algorithm Strategy: Bit Manipulation Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 389

Java Solution for LeetCode 389

Python Solution for LeetCode 389

Practise Find the Difference and the problems around it

Related problems

Find the Difference

Core insight

Core Insight for Find the Difference

Full breakdown

LeetCode 389: Find the Difference Solution & Explanation

Problem Overview

Brute Force Approach for Find the Difference

Algorithm Strategy: Bit Manipulation Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 389

Java Solution for LeetCode 389

Python Solution for LeetCode 389

Practise Find the Difference and the problems around it

Related problems