LESSON 398 OF 442 · BIT MANIPULATION

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

Guided

Ctrl + Enter to check

Find The Difference in Scala, explained

Problem overview

The string t is s shuffled with one extra lowercase letter inserted. The method findTheDifference(s: String, t: String): Char must return that letter: 'e' for s = "abcd" and t = "abcde", and 'y' for s = "" and t = "y".

The lesson asks for O(n) time and O(1) extra space. Counting letters in a map is O(n) time too, but it needs a structure that holds the counts. XOR needs one integer.

Approach: letters that appear twice cancel out

Every character is a number, its character code. XOR, written ^ in Scala, combines two integers bit by bit: a result bit is 1 when the two input bits differ. Three properties matter:

x ^ x = 0: a number XOR itself is zero.
x ^ 0 = x: XOR with zero changes nothing.
The order of the operands doesn't matter, and neither does how they are grouped.

Start with 0 and XOR in the code of every character of s, then of every character of t. Every letter of s has an equal partner in t, so the codes come in matching pairs. Because of the order-free property, the pairs can be imagined next to each other, and each pair gives 0. The one letter without a partner is the extra one, and it is what remains. Turning that number back into a Char gives the answer.

Take s = "aab" and t = "baab". The values XORed are a, a, b, b, a, a, b in some order: a appears four times and b three times. The four a values cancel in pairs, two of the b values cancel, and one b is left, so the result is the code of 'b'. Duplicates are no problem: an extra copy of a letter simply makes its total count odd.

Step by step

Declare an accumulator. var result = 0 is an Int, and it starts at 0 because 0 ^ x = x leaves the first value unchanged.
Loop over s. The loop variable c is each character.
XOR each character in. result ^= c combines the accumulator with the character's code. A Char widens to Int for the operation, and the result stays an Int.
Loop over t. Again the variable is c.
XOR those in too. After this loop, every letter that occurs in both strings has been XORed an even number of times and has cancelled. Only the extra letter, XORed one time more than its partners, survives.
Convert back. result.toChar turns the integer code into the Char the method returns.

The solution in Scala

class Solution {
    def findTheDifference(s: String, t: String): Char = {
        var result = 0
        for (c <- s) {
            result ^= c
        }
        for (c <- t) {
            result ^= c
        }
        return result.toChar
    }
}

The Scala details worth a closer look:

Char and Int. In Scala a Char is a 16-bit unsigned number that is shown as a character. 'a' ^ 'b' is an Int (the value 3), and result ^= c works because the compiler widens c to an Int first. The accumulator has to be an Int.
^=. It is the compound assignment for result = result ^ c and requires result to be a var.
toChar. Going from Int back to Char is not automatic, because it can lose information. (97 ^ 97 ^ 101).toChar gives 'e'. Here the value is always a valid lowercase letter code, so nothing is lost.
Loops over strings. for (c <- s) walks a String character by character, giving Char values.
return in the method. The final return is not inside a loop, so it is an ordinary return. The method's last expression, result.toChar, would give the same value without the keyword.

Complexity

Time: O(n). The loops visit n - 1 and n characters, with one XOR each. XOR on an Int takes constant time.

Space: O(1). One Int accumulator, plus the loop variable. The method builds no map, array or copy of the strings.

Edge cases and common mistakes

Empty s. The first loop does nothing, and the second XORs the single character of t into 0. The result is that character's code, so s = "" and t = "y" give 'y'.
A duplicate extra letter. For s = "z" and t = "zz", the three z values leave one z, and the method returns 'z'. No special handling is needed.
Returning the number. The method must return a Char. Leaving off toChar gives a compile error, Found: (result : Int) and Required: Char.
Starting from a nonzero value. The accumulator must start at 0. Any other start value stays in the result, and toChar would return the wrong letter.
Adding instead of XOR. Using + does not cancel anything. Summing the codes of t and subtracting the sum for s would also work, but XOR cannot overflow and so it is the cleaner tool.
Only for exactly one extra letter. XOR works because all other letters come in pairs. If the input broke that rule, the result would be meaningless.

Testing

s = "abcd", t = "abcde" returns 'e'.
s = "", t = "y" returns 'y'.
s = "aab", t = "baab" returns 'b'.
s = "z", t = "zz" returns 'z'.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free