Start learning free

LESSON 394 OF 438 · BIT MANIPULATION

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

JAVA · BIT MANIPULATION

Find The Difference in Java, explained

Problem overview

The method findTheDifference(String s, String t) receives two strings of lowercase letters. The string t is s shuffled, with one extra letter added somewhere. The method returns that extra letter as a char. The length of s is from 0 to 1000, and t is one longer.

For s = "abcd" and t = "abcde" the result is 'e', and for s = "" and 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: XOR cancels the pairs

Counting letters with a hash map is already linear, but it keeps a map. XOR, written ^ in Java, gets the answer with a single number. It combines two numbers bit by bit: a result bit is 1 when the two input bits differ. Three facts matter here:

x ^ x is 0: a number cancels itself.
x ^ 0 is x: zero changes nothing.
The order does not matter, so XORing a list of numbers gives the same result in any order.

Every letter has a character code, a number. Start with 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 because order doesn't matter, each pair meets and cancels to 0. The one letter without a partner is the extra one. XORing it with 0 leaves its own code, and that code is the answer.

For s = "abcd" and t = "abcde": the codes of a, b, c, d appear twice and cancel, and e (code 101) appears once. The running value ends at 101, which is 'e'. For a repeated extra letter such as s = "aa" and t = "aaa", the code of 'a' appears five times: two pairs cancel and one copy is left.

Step by step

Declare result as a char set to 0. It is the accumulator. Zero is the neutral value for XOR, so the first letter XORed in simply becomes the value.
Loop over the letters of s with s.toCharArray(), naming each one c.
XOR each letter into result with result ^= c.
Loop over the letters of t the same way.
XOR each of those in too. After this loop, every letter that has a partner has been XORed in an even number of times and has vanished.
Return result. It already has type char, so no conversion is needed.

The solution in Java

class Solution {
    public char findTheDifference(String s, String t) {
        char result = 0;
        for (char c : s.toCharArray()) {
            result ^= c;
        }
        for (char c : t.toCharArray()) {
            result ^= c;
        }
        return result;
    }
}

The Java details worth a look:

char is a number. A Java char is an unsigned 16-bit number, so char result = 0; is legal and bitwise operators work on it. Printing result shows the letter, while (int) result shows its code.
^= keeps the type. Java promotes the operands of ^ to int, so result ^ c is an int. The compound form result ^= c casts the answer back to char automatically. The long form does not compile:

char result = 0;
char c = 'e';
result = result ^ c;   // does not compile
result = (char) (result ^ c);   // compiles

The compiler reports incompatible types: possible lossy conversion from int to char for the first assignment. The cast in the second line fixes it, and ^= does that cast for you.

No fallback return. Unlike the hash-map version, this method always ends at the final return result;, so there is no unreachable code.
Two loops, one accumulator. The loops could run in the other order, because XOR doesn't care about order.

Complexity

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

Space: O(1). The only state is one char. The toCharArray() calls do allocate copies of the strings, so if you want strictly constant space, use s.charAt(i) in an index loop instead. The XOR logic stays the same.

Edge cases and common mistakes

An empty s. Only the letter of t is XORed into 0, so ("", "y") gives 'y'.
A repeated extra letter. ("aa", "aaa") gives 'a': five copies of the code, two pairs cancel, one is left.
Writing result = result ^ c. It fails to compile, as shown above. Use ^= or add the cast.
Starting from a non-zero value. The accumulator must start at 0. Any other start would be XORed into the answer and change it.
Using + or - instead of XOR. Adding the codes of t and subtracting the codes of s into an int also finds the letter. XOR does the same with a plain char and can never overflow, since the result always fits in 16 bits.
Using it when more than one letter is extra. XOR only isolates one lonely letter. If two letters were added, their codes would be mixed together in the result.

Testing

"abcd", "abcde" gives 'e'.
"", "y" gives 'y'.
"aa", "aaa" gives 'a'.
"abcd", "dbeca" gives 'e'.

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

Start learning free