Problem overview
The method findTheDifference(s, t) receives two strings of lowercase letters. The string t is s shuffled, with one extra letter inserted somewhere. The method returns that extra letter as a one-character string.
For s = "abcd" and t = "abcde" the answer is "e", and for s = "" and t = "y" the answer is "y". The string s may be empty, and t is always one character longer.
This lesson asks for O(n) time and O(1) extra space, where n is the length of t.
Approach: let equal letters cancel each other
Counting letters with a table reaches O(n) time, and since the alphabet has 26 letters, the table is bounded too. This lesson goes further and keeps no table at all: a single number does the whole job.
The tool is the XOR operator, ^. It works on the bits of two numbers, and it has three properties that matter here:
x ^ xis0: a number cancels itself.x ^ 0isx: XOR with zero changes nothing.- The order doesn't matter:
a ^ b ^ cequalsc ^ a ^ b.
Every letter has a character code, a number. Start at 0 and XOR in the code of every letter of s, then the code of every letter of t. Each letter of s has an equal partner in t, and because the order is irrelevant, each pair cancels to 0 wherever its two letters sit. The only code with no partner is the extra letter's, so it is all that remains. Turn that number back into a character and it is the answer.
Here is a small run with s = "ab" and t = "bca", where the extra letter is c. The codes are a = 97, b = 98 and c = 99:
letter code result after XOR
a 97 97
b 98 3
b 98 97
c 99 2
a 97 99
The final value is 99, which is the code of c. The two b codes cancelled, the two a codes cancelled, and 99 stayed.
Step by step
- Declare
resultwithletand start it at 0. It is the accumulator. Starting from 0 is right because0 ^ xis justx, so the first XOR doesn't disturb the value. - Loop over
swithfor...of, one character at a time. - XOR in each character's code. The method
c.charCodeAt(0)returns the numeric code of the character at position 0 of the one-character stringc, and^=combines it intoresultin place. - Loop over
tthe same way. - XOR in the codes of
t. After this loop, every letter that appears in both strings has been mixed in twice and is gone. - Convert the number back to a letter with
String.fromCharCode(result), which builds a one-character string from a code.
The solution in JavaScript
class Solution {
findTheDifference(s, t) {
let result = 0;
for (const c of s) {
result ^= c.charCodeAt(0);
}
for (const c of t) {
result ^= c.charCodeAt(0);
}
return String.fromCharCode(result);
}
}
Some JavaScript details worth a closer look:
^is XOR, not a power. JavaScript's exponent operator is**. The expression5 ^ 5is0, and5 ^ 0is5.- Bitwise operators work on 32-bit integers. JavaScript numbers are doubles, but
^first converts each operand to a 32-bit integer. Letter codes are small, so nothing is lost here. charCodeAttakes an index and returns a number."a".charCodeAt(0)is97. If the index is out of range, such as"".charCodeAt(0), the result isNaN, and that is a reason to loop over real characters rather than guess indexes.String.fromCharCodeis the reverse.String.fromCharCode(99)is"c". It returns a string, which is what the lesson expects, not a number.- Compound assignment.
result ^= xmeansresult = result ^ x, the same shorthand as+=.
Complexity
Time: O(n). The method makes one pass over s and one over t, and each step is a single XOR on small numbers. The total is about 2n steps, which is O(n).
Space: O(1). The method keeps one number, result, plus the loop variable. It builds no table, array or new string, apart from the one-character string it returns.
Edge cases and common mistakes
- An empty
s. The first loop does nothing, the second XORs in the one letter oft, and the method returns it. Fort = "y"the answer is"y". - The extra letter repeats an existing one. For
s = "aab"andt = "abaa", threeacodes and onebcode meet. Pairs cancel, and oneais left, so the answer is"a". Odd and even counts are what XOR sees, and that is enough here. - Returning the number. The accumulator holds a code such as
101. WithoutString.fromCharCodethe method returns that number instead of"e". - Using
+instead of^. Adding all the codes of both strings gives a sum that doesn't cancel. The addition version needs subtraction: add the codes oftand subtract the codes ofs, and the difference is the extra code. XOR gets the same effect without sign worries. - Starting
resultfrom something other than 0. Any other start value stays in the result, so the final code would be wrong. - Applying the idea to other inputs. XOR cancels exactly pairs. The trick works because every letter of
shas exactly one equal partner int. If the input could have more than one extra letter, the result would be a mix of their codes and would not identify any of them.
Testing
s = "abcd",t = "abcde"gives"e".s = "",t = "y"gives"y".s = "aab",t = "abaa"gives"a".s = "ab",t = "bca"gives"c".
