Start learning free

LESSON 401 OF 445 · BIT MANIPULATION

Find the Difference in Rust: 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

    RUST · BIT MANIPULATION

    Find The Difference in Rust, explained

    Problem overview

    The function find_the_difference receives two string slices. The string t is s shuffled, plus one extra lowercase letter at a random position. The function returns the extra letter as a char. The string s can be empty.

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

    Approach: letters that pair up cancel under XOR

    Counting letters works, but a count table is extra data. XOR (^ in Rust) gives an answer with a single number. The operation works on the bits of two integers and has three properties that matter here:

    • x ^ x = 0: a number XORed with itself disappears.
    • x ^ 0 = x: XOR with zero changes nothing.
    • The order doesn't matter, so the numbers can be combined in any sequence.

    Every letter has a numeric code, its byte value. XOR the code of every letter of s and every letter of t into one accumulator that starts at 0. A letter that occurs in both strings is XORed in once for each copy in s and once for each copy in t, which is an even number of times, so it cancels completely. The extra letter is XORed in one more time than its partners can cancel, so its code is the only thing left.

    On s = "ab" and t = "abb" the accumulator sees a, b, a, b, b. The two a values cancel, two of the three b values cancel, and the third b remains.

    A look at the bits

    The code of a is 97, or 01100001 in binary, and the code of e is 101, or 01100101. Their XOR is 00000100, because XOR gives 1 only where the bits differ. XORing 97 with itself gives 0, and XORing it with 0 gives 97 back.

    Step by step

    1. Declare the accumulator as let mut result: u8 = 0;. A u8 is exactly one byte, the size of a lowercase ASCII letter's code, and XOR of two u8 values is another u8.
    2. Loop over s.bytes() with the variable c. The bytes() method yields each byte of the string as a u8, which supports XOR directly.
    3. XOR each byte in with result ^= c;.
    4. Loop over t.bytes() the same way.
    5. XOR those bytes in too. After this loop every paired letter has cancelled.
    6. Convert the leftover byte to a char with result as char and return it as the last expression of the function.

    The solution in Rust

    impl Solution {
    fn find_the_difference(s: &str, t: &str) -> char {
        let mut result: u8 = 0;
        for c in s.bytes() {
            result ^= c;
        }
        for c in t.bytes() {
            result ^= c;
        }
        result as char
    }
}

    It returns 'e' for ("abcd", "abcde"), 'y' for ("", "y") and 'q' for ("xyz", "zyxq").

    The Rust details worth a closer look:

    • bytes() versus chars(). chars() yields char values, which do not support ^. bytes() yields u8 values, which do. For lowercase English letters, each letter is exactly one byte, so the two views agree.
    • Only u8 can be cast to char. 98u8 as char is 'b'. A wider integer is rejected: casting a u32 with as char stops the build with the error "only u8 can be cast as char, not u32", and suggests char::from_u32. That is a good reason to keep the accumulator a u8.
    • No overflow is possible. XOR never carries, so a u8 accumulator stays within 0 to 255 whatever is combined into it.
    • ^= is the compound assignment form of ^, like += for addition. The variable must be mut.
    • The last expression. result as char has no semicolon, so it is the function's value. No return is needed, and no placeholder either: the function always has a leftover value to return.

    Complexity

    Time: O(n). Each string is read once, with one XOR per byte, giving about 2n - 1 operations.

    Space: O(1). One u8 accumulator, whatever the length of the strings. Compared with the hash map solution, there is no table at all, though the map's size was already bounded by 26 entries.

    Edge cases and common mistakes

    • Empty s. Only t contributes, and it has a single letter. ("", "y") gives 'y'.
    • The extra letter equals one already present. For ("aa", "aaa"), the three a codes XOR to a in the end: two cancel and one stays. The method needs no special case for repeats.
    • Starting the accumulator at something other than 0. Any other start value would remain in the result, because it is never cancelled.
    • Skipping one of the two loops. With only t XORed in, the result is the XOR of all its letters, not the extra one.
    • Using chars() and casting each char to u8. That works for ASCII, but as u8 silently truncates larger code points. Iterating over bytes() avoids the cast.
    • Relying on XOR for other shapes of input. The trick needs every other letter to appear an even number of times in total, as the problem guarantees. If t had two extra letters, the result would be the XOR of both, which is not a letter you could name.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "ab", t = "abb" gives 'b'.
    • s = "aa", t = "aaa" gives 'a'.
    • s = "xyz", t = "zyxq" gives 'q'.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free