Start learning free

LESSON 394 OF 438 · BIT MANIPULATION

Find the Difference in Python: 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 character.

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

    PYTHON · BIT MANIPULATION

    Find The Difference in Python, explained

    Problem overview

    The method findTheDifference receives two strings, s and t. The string t is s shuffled, plus one extra lowercase letter at a random position. The method returns that letter. s may be empty, and t is exactly one character longer than s.

    For s = "abcd" and t = "abcde" the answer is "e", and for s = "" and t = "y" it is "y". This lesson asks for O(n) time and O(1) extra space.

    Approach: let equal letters cancel out

    Counting letters with count() costs O(n²), and a dictionary of counts gets to O(n) time. Both work, but there is a shorter idea that needs only one integer.

    Every character has a numeric code, which Python returns from ord(): ord('a') is 97 and ord('e') is 101. The XOR operator ^ combines two integers bit by bit, and it has three properties that matter here:

    • x ^ x == 0: a number XORed with itself disappears;
    • x ^ 0 == x: XOR with 0 changes nothing;
    • the order does not matter, so a ^ b ^ a equals b.

    Now XOR the codes of every letter of s and every letter of t into one number that starts at 0. Each letter of s has a matching letter in t, so the two codes cancel to 0 wherever they sit in the strings. Only the extra letter has no partner, so its code is all that remains. Converting it back with chr() gives the answer.

    With s = "ab" and t = "aba", the codes are 97, 98 and 97, 98, 97. The two 97s from the matching pair cancel, as do the two 98s, and one 97 is left. chr(97) is "a", which is the extra letter.

    Step by step

    1. Start an accumulator named result at 0. Because x ^ 0 == x, 0 is the neutral starting value.
    2. Loop over s with the variable c.
    3. XOR in each code. ord(c) turns the letter into an integer, because ^ works on numbers, not on strings. ^= updates result in place.
    4. Loop over t in the same way.
    5. XOR in each code again. After this loop, every letter that appears in both strings has been XORed an even number of times in total and has cancelled. The extra letter was XORed one more time than it appears in s, so it survives.
    6. Convert back. chr(result) turns the remaining code into a one-character string and returns it.

    The solution in Python

    class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        result = 0
        for c in s:
            result ^= ord(c)
        for c in t:
            result ^= ord(c)
        return chr(result)

    Python details worth knowing:

    • ord and chr are inverses. ord("e") is 101 and chr(101) is "e". Without ord, result ^= c would raise a TypeError, since an integer cannot be XORed with a string.
    • ^ is XOR, not a power. Exponentiation in Python is **.
    • Python integers don't overflow. The codes of lowercase letters are between 97 and 122, and XOR of numbers below 128 stays below 128, so chr always receives a valid code.
    • Order is irrelevant. The two loops could be swapped, or merged over both strings, and the result would be the same.

    Complexity

    Time: O(n). The loops perform one XOR per letter, n - 1 letters for s and n for t, and each XOR takes constant time.

    Space: O(1). The only state is the integer result and the loop variable. Unlike the dictionary approach, nothing depends on the alphabet size at all.

    Edge cases and common mistakes

    • Empty s. The first loop does nothing, result is still 0, and the second loop sets it to the code of the single letter in t. For t = "y" the answer is "y".
    • The extra letter equals an existing one. With s = "aab" and t = "abaa", three a codes and one b are XORed from t and two a codes and one b from s. Pairs cancel, and one a remains. XOR needs no special case for this.
    • Using + instead of ^. Adding the codes of both strings does not cancel them. A sum of t minus a sum of s would work, but that is a different approach.
    • Forgetting ord or chr. Without ord the XOR fails with a TypeError. Without chr the method returns a number such as 101 instead of "e".
    • Relying on valid input. The cancellation works only because t contains exactly the letters of s plus one. For other inputs the result is just the XOR of whatever is left.

    Testing

    • s = "abcd", t = "abcde" gives "e".
    • s = "", t = "y" gives "y".
    • s = "ab", t = "aba" gives "a".
    • s = "abcd", t = "dcbae" gives "e".
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free