Start learning free

LESSON 398 OF 442 · BIT MANIPULATION

Find the Difference in Go: O(n) Time, 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 rune.

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

    GO · BIT MANIPULATION

    Find The Difference in Go, explained

    Problem overview

    The string t is s shuffled with one extra lowercase letter inserted. findTheDifference(s string, t string) returns that letter as a rune. The string s may be empty.

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

    Approach: let equal letters cancel

    Counting with a map already runs in O(n) time. This lesson does without the map, using the XOR operator, ^ in Go. XOR compares two numbers bit by bit and gives a 1 where the bits differ. Three of its properties solve this problem:

    • x ^ x is 0: a number cancels itself.
    • x ^ 0 is x: zero changes nothing.
    • Order and grouping don't matter, so a ^ b ^ a equals b even though the two a values are not next to each other.

    Every letter has a number, its code point. Start an accumulator at 0 and XOR in the code of every letter of s and then of every letter of t. Each letter of s has an equal partner in t, and the shuffle doesn't matter because order is irrelevant to XOR. The partners cancel to 0 in pairs, and the one letter without a partner is left. If a letter occurs three times in t and twice in s, two of the three cancel against the two in s, and one remains.

    For s = "abcd" and t = "abcde" the accumulator ends as a ^ b ^ c ^ d ^ a ^ b ^ c ^ d ^ e, which is e, the number 101.

    Step by step

    1. Declare the accumulator as var result rune = 0. It has to be a rune, because XOR in Go needs both operands to have the same type and the letters from range are runes.
    2. Loop over s with for _, c := range s. The loop yields each letter as a rune, and _ ignores the position.
    3. XOR each letter in with result ^= c, shorthand for result = result ^ c.
    4. Loop over t the same way.
    5. XOR those letters in too. After this loop, every letter that appears in both strings has been mixed in twice per matching pair and has cancelled out.
    6. Return result. It already has the right type, so no conversion and no fallback return are needed.

    The solution in Go

    func findTheDifference(s string, t string) rune {
    var result rune = 0
    for _, c := range s {
        result ^= c
    }
    for _, c := range t {
        result ^= c
    }
    return result
}

    The Go details worth a closer look:

    • ^ is XOR when written between two operands. In Go, the same symbol also has a unary form: ^x flips every bit of x. Go has no ~ operator. Here result ^= c uses the binary compound form.
    • Types must match. Mixing a byte and a rune, as in x ^ r with a uint8 and a rune, doesn't compile: invalid operation: x ^ r (mismatched types uint8 and rune). That is why the accumulator is a rune rather than an int or a byte.
    • The answer is a number. Returning rune means fmt.Println prints 101 for e. Use string(r) or fmt.Printf("%c", r) to show the letter.
    • No extra return. The earlier solutions need a fallback return ' ', because a return inside a loop might never run as far as the compiler can tell. This version always reaches the final return.
    • No overflow worry. XOR never carries, so the result stays within the range of the inputs.

    Complexity

    Time: O(n). One XOR per letter, over s and then t, which is about 2n cheap operations. There are no lookups or sorting.

    Space: O(1). The only extra memory is the single rune accumulator. The brute-force version also used O(1) space but needed O(n²) time, and the map version needed a map of up to 26 entries.

    Edge cases and common mistakes

    • Empty s. Nothing is XORed in the first loop, and the second loop leaves just the code of the single letter in t.
    • The extra letter repeats another one. s = "aab", t = "abaa" returns a: a appears 5 times in total, so one is left after the pairs cancel.
    • Starting the accumulator at 1 or any other nonzero value. That value would be XORed into the answer. Start at 0.
    • Relying on the idea elsewhere. XOR cancellation finds the odd one out. Here it works because every other letter occurs an even number of times in total across the two strings.

    Testing

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