Start learning free

LESSON 398 OF 442 · BIT MANIPULATION

Find the Difference in TypeScript: 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 character.

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

    TYPESCRIPT · BIT MANIPULATION

    Find The Difference in TypeScript, explained

    Problem overview

    String t is a shuffled copy of s plus one extra lowercase letter, and findTheDifference returns the extra letter. For s = "abcd" and t = "abcde" the answer is "e". For s = "" and t = "y" it is "y".

    This version has a stricter budget: O(n) time and O(1) extra space. A table of letter counts fits in constant space for 26 letters, but this lesson avoids even that and uses a single number.

    Approach: let equal letters cancel

    Every letter has a numeric code, and the bitwise XOR operator ^ combines two numbers bit by bit. Three properties of XOR matter here:

    • x ^ x is 0: a number cancels itself.
    • x ^ 0 is x: XOR with 0 changes nothing.
    • The order doesn't matter: XOR is commutative and associative, so the numbers can be combined in any sequence and grouping.

    Start an accumulator at 0 and XOR in the code of every letter of s, then of every letter of t. Each letter of s has an equal partner in t, and each such pair is XORed in twice. Because order doesn't matter, you can imagine the pairs next to each other, where each pair becomes 0. Only the extra letter has no partner, so its code is what remains. Turning that code back into a string gives the answer.

    For s = "ab" and t = "bax", the codes a, b, b, a, x are combined. The two a codes cancel, the two b codes cancel, and the code of "x" is left. It makes no difference that t is shuffled.

    Step by step

    1. Start result at 0. It is the identity for XOR, so it doesn't affect the first value combined into it. Use let, since it changes.
    2. Loop over the letters of s with for...of, naming each letter c.
    3. Combine each code into result with result ^= c.charCodeAt(0). charCodeAt(0) gives the number for the first (here the only) character of c.
    4. Loop over the letters of t in a second loop.
    5. Do the same inside it. After this loop, every letter that occurs in both strings has been XORed in an even number of times and has vanished.
    6. Convert the code back with String.fromCharCode(result) and return it.

    The solution in TypeScript

    class Solution {
    findTheDifference(s: string, t: string): string {
        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);
    }
}

    The TypeScript details worth a closer look:

    • Letters are strings. TypeScript has no character type and ^ only works on numbers, so each letter must be turned into a code first. "e".charCodeAt(0) is 101.
    • ^= is shorthand. result ^= x means result = result ^ x.
    • Numbers are doubles, but XOR works on 32 bits. JavaScript's number is a double, and bitwise operators convert their operands to 32-bit integers first. Letter codes are far below that limit, so nothing is lost. The result is also a small non-negative number, which String.fromCharCode turns into a one-character string.
    • Inferred types. let result = 0 is inferred as number, and for...of over a string gives each c as a string, so no annotations are needed.
    • No lookup table. Unlike the object-based approach, nothing here depends on which letters occur.

    Complexity

    Time: O(n). There is one XOR per letter of s and one per letter of t, so about 2n cheap operations.

    Space: O(1). The method keeps a single number and the loop variable. Nothing grows with the input.

    Edge cases and common mistakes

    • Empty s. The first loop leaves result at 0, and the second XORs in the code of the only letter of t. The result is that code, so "y" comes back.
    • The extra letter repeats one in s. For s = "a" and t = "aa", the code of "a" is XORed three times. Two of them cancel and one remains, so "a" is returned.
    • Shuffled order. The shuffling in t doesn't matter, because XOR is commutative.
    • Starting from something other than 0. A nonzero start value would leave itself mixed into the result.
    • Using + instead of ^. Addition doesn't cancel equal letters. Subtracting the sum of s from the sum of t would also work, but that is a different idea.
    • Forgetting the conversion. Returning result directly would return a number, not the letter.

    Testing

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