Start learning free

LESSON 397 OF 441 · 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 method FindTheDifference receives two strings of lowercase letters, s and t. The string t is s shuffled with one extra letter added. The method returns that extra letter as a char, in O(n) time and with O(1) extra space.

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

    Approach: let equal letters cancel

    Counting letters with a dictionary is linear in time, but it stores counts. This lesson needs constant space and uses the bitwise XOR operator, ^, which has three properties:

    • x ^ x is 0: a value cancels itself.
    • x ^ 0 is x: XOR with zero changes nothing.
    • The order doesn't matter: a ^ b ^ c equals c ^ a ^ b.

    Every letter has a numeric code, its UTF-16 value, and 'a' is 97. XOR together the codes of all letters of s and all letters of t. Each letter of s has an equal partner in t, and because the order is irrelevant, each such pair cancels to 0. Only the extra letter has no partner, so the final value is its code. Converting that value back to a char gives the answer.

    For s = "abcd" and t = "abcde": the letters a, b, c and d each appear twice in total and cancel, leaving 0 ^ 'e', which is 101, the code of 'e'.

    Step by step

    1. Declare an accumulator char result = (char)0;. Starting at 0 is safe because XOR with 0 leaves any value unchanged. The cast turns the integer 0 into the char with code 0.
    2. Loop over s with foreach (char c in s).
    3. XOR each letter into the accumulator with result ^= c;.
    4. Loop over t the same way.
    5. XOR each of its letters in too. After this loop, every letter that occurs in both strings has been XOR-ed an even number of times and has cancelled.
    6. Return result. It holds the code of the extra letter, and it is already a char, so no conversion is needed.

    The solution in C#

    class Solution {
    public char FindTheDifference(string s, string t) {
        char result = (char)0;
        foreach (char c in s) {
            result ^= c;
        }
        foreach (char c in t) {
            result ^= c;
        }
        return result;
    }
}

    The C# details worth knowing:

    • ^ on char values produces an int. C# converts char operands to int before doing arithmetic or bitwise operations. So 'a' ^ 'b' has type int (here, 3).
    • Why ^= works and result = result ^ c doesn't. Writing result = result ^ c; with result a char is a compile error: Cannot implicitly convert type 'int' to 'char'. An explicit conversion exists (are you missing a cast?). The compound form result ^= c converts the int back to char for you. The long form needs a cast: result = (char)(result ^ c);.
    • Values stay in range. Both operands are 16-bit values, and the XOR of two 16-bit values fits in 16 bits, so the conversion back to char never loses anything.
    • The order is free. XOR in t first and s second and the result is the same.
    • The accumulator can be an int. Declaring int result = 0 and returning (char)result is equivalent. The lesson keeps it a char so that the return needs no conversion.

    Complexity

    Time: O(n). Each letter of s and t is read once, and one XOR costs constant time.

    Space: O(1). The only extra memory is result and the loop variable. There is no dictionary or array that grows with the input.

    Edge cases and common mistakes

    • Empty s. The first loop does nothing, and the second XORs the single letter of t into 0. s = "", t = "y" gives 'y'.
    • The extra letter repeats a letter of s. For s = "aab" and t = "baab", the letter a appears four times in total and b three times. The four as cancel in pairs, and two of the three bs cancel, leaving 'b'.
    • Using + instead of ^. Adding the codes of t and subtracting the codes of s also finds the letter, but XOR needs no subtraction and no sign to think about.
    • Starting from a letter instead of 0. The accumulator must start at 0, or its starting value stays mixed into the answer.
    • Assuming it works for any input. XOR cancels exact pairs. It relies on the guarantee that t is s plus one letter. If the strings broke that rule, the result would be meaningless.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "aab", t = "baab" gives 'b'.
    • s = "ab", t = "bca" gives 'c'.
    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