Start learning free

LESSON 393 OF 437 · BIT MANIPULATION

Find the Difference in C++: O(1) Space with XOR

Practice O(n) / O(1) Read the full explanation

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

 

Example 1:

Input: s = "abcd", t = "abcde"
Output: e
Explanation: 'e' is the letter that was added.

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.
Note:

For this lesson, your algorithm should run in O(n) time and use O(1) extra space, where n is the length of t.



Every letter has a code number. XOR on two numbers has two useful properties: x XOR x = 0 and x XOR 0 = x, and the order of the numbers doesn't matter.

Start from 0 and XOR in the code of every letter of s and of every letter of t. Each letter of s has an equal partner in t, so the pairs cancel out. What is left is the code of the extra letter: turn it back into a char.

We walk through s once and t once, one XOR per letter: O(n) time.
We keep a single number, so the extra space is O(1).
STEP 1 OF 6
    Ctrl + Enter to check

    C++ · BIT MANIPULATION

    Find The Difference in C++, explained

    Problem overview

    The string t is s shuffled, plus one extra lowercase letter inserted at a random position. findTheDifference returns the extra letter as a char. The string s can be empty and t is exactly one character longer.

    For s = "abcd" and t = "abcde" the result is 'e'. For s = "" and t = "y" it is 'y'.

    This lesson asks for O(n) time and O(1) extra space, where n is the length of t. That rules out counting letters in a hash table whose size depends on the input, and it points to a trick with bitwise XOR.

    Approach: let paired letters cancel out

    XOR, written ^ in C++, combines two integers bit by bit: each result bit is 1 when the two input bits differ. Two properties matter here:

    • x ^ x = 0: any value XORed with itself gives zero.
    • x ^ 0 = x: XOR with zero changes nothing.

    XOR is also commutative and associative, so the order in which values are combined doesn't matter.

    Now XOR every character of s and every character of t into one accumulator. Each letter of s appears once in s and once in its shuffled copy inside t, so every such pair cancels to zero, wherever the letters sit in the strings. The only letter without a partner is the extra one in t, and what is left in the accumulator is exactly that letter.

    Repeated letters work the same way. With s = "aab" and t = "abaa", the letters XORed together are a, a, b, a, b, a, a. That is five copies of a (three from t and two from s) and two of b. The two bs cancel, four of the five as cancel, and one a remains.

    The method needs one variable and two passes, so the extra space is constant and the time is O(n).

    Step by step

    1. Declare char result = 0. Zero is the identity for XOR, so the accumulator starts out neutral.
    2. Loop over s with a range-based for, naming each character c.
    3. XOR each character into result with ^=.
    4. Loop over t the same way.
    5. XOR each of its characters into result as well. After this loop every letter that occurs in both strings has been combined twice per pair and has cancelled.
    6. Return result. It holds the extra letter, so no fallback return is needed.

    The solution in C++

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

    C++ details worth a closer look:

    • Characters are integers. A char holds a character code, such as 97 for 'a', so XOR works on it directly. In an expression, both operands of ^ are first promoted to int.
    • Compound assignment narrows for you. result ^= c computes the XOR as an int and stores it back into the char. Writing result = result ^ c compiles too, but a narrowing from int to char is easier to notice there. Because the inputs are lowercase letters, with codes from 97 to 122, every value stays well inside the range of a char, whether char is signed or unsigned on the platform.
    • Both strings, one accumulator. The order of the two loops doesn't matter. You could also loop over t first, or interleave the work in a single loop over t with an index into s.
    • No fallback return. Unlike the counting solutions, this function has no early return inside a loop, so the last line is the only exit.
    • Strings by value. The parameters are copies of the caller's strings. The method only reads them.

    Complexity

    Time: O(n). The loops run n - 1 and n times, and each step is one XOR.

    Space: O(1) extra. The only added storage is the char result. The by-value string parameters are copies made by the call itself, and taking them as const string& would avoid that cost as well.

    Edge cases and common mistakes

    • Empty s. The first loop does nothing, and the second leaves exactly the single character of t, so 'y' comes back for t = "y".
    • The extra letter is a duplicate. With s = "a" and t = "aa" the three as XOR to 'a'. No special case is needed, which is the strength of this method.
    • Skipping one of the strings. XORing only t gives the XOR of all its letters, not the extra one. Both strings must go into the accumulator.
    • Starting from a non-zero value. The accumulator must start at 0. Any other start leaves a stray value in the result.
    • Using + or - instead of ^. Addition doesn't cancel pairs, so summing both strings just adds everything up. Subtracting the sum of s from the sum of t does give the extra letter's code, but that is a different technique, and XOR avoids any question of overflow.
    • Input outside the contract. The result is only meaningful when t really is a shuffle of s plus one letter. With other inputs XOR just returns the XOR of the unmatched characters.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "aab", t = "abaa" gives 'a'.
    • s = "a", t = "ab" gives 'b'.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free