Start learning free

LESSON 398 OF 442 · BIT MANIPULATION

Find the Difference in Kotlin: 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
    Ctrl + Enter to check

    KOTLIN · BIT MANIPULATION

    Find The Difference in Kotlin, explained

    Problem overview

    findTheDifference(s, t) takes two strings of lowercase letters. The string t is s shuffled with one extra letter added somewhere, and the function returns that letter as a Char.

    With s = "abcd" and t = "abcde" the result is 'e', and with s = "" and t = "y" it is 'y'. This lesson requires O(n) time and O(1) extra space, where n is the length of t. That rules out a map of counts, which needs space for the letters, and points to a trick with bits.

    Approach: let equal letters cancel with XOR

    Every character has a numeric code. In Kotlin, c.code gives it as an Int: 'a'.code is 97, 'b'.code is 98 and 'e'.code is 101.

    The bitwise XOR operation combines two numbers bit by bit, giving a 1 where the bits differ and a 0 where they match. Three of its properties solve this problem:

    • A number XOR itself is 0, because every bit matches: 5 xor 5 is 0.
    • A number XOR 0 is unchanged: 5 xor 0 is 5.
    • The order doesn't matter, so you can group numbers freely.

    Now picture XOR-ing the codes of all letters of s and then all letters of t. Each letter of s has an identical partner in t, and the order of the letters is irrelevant, so each pair cancels to 0. One letter of t has no partner. Everything else cancels, and what is left is the code of the extra letter. Converting that number back to a Char gives the answer.

    Take s = "ab" and t = "bab". XOR-ing 97, 98 from s and 98, 97, 98 from t gives the same value as pairing them up: 97 cancels with 97, one 98 cancels with the other 98, and the last 98 is left. The function returns 'b'. Duplicates are no problem, since an extra copy of a letter that s already has simply remains unpaired.

    Unlike the counting approaches, this one doesn't care how large the alphabet is, and it needs no table at all.

    Step by step

    1. Declare the accumulator. var result = 0 is an Int that every code will be folded into. It starts at 0 because XOR with 0 changes nothing.
    2. Loop over s. for (c in s) visits each letter.
    3. Fold each code in. result = result xor c.code updates the running value.
    4. Loop over t. The same loop and the same fold run over the second string.
    5. Fold in t's codes. Each letter that appears in both strings has now been XOR-ed in twice.
    6. Convert and return. result.toChar() turns the leftover code back into a letter.

    The solution in Kotlin

    class Solution {
    fun findTheDifference(s: String, t: String): Char {
        var result = 0
        for (c in s) {
            result = result xor c.code
        }
        for (c in t) {
            result = result xor c.code
        }
        return result.toChar()
    }
}

    Kotlin details worth a look:

    • xor is a function, not a symbol. Kotlin has no ^ operator for bits. xor is an infix function on the integer types, so a xor b is the same as a.xor(b).
    • Char has no xor. Writing 'a' xor 'b' fails with unresolved reference 'xor'. You first take the numeric value with .code.
    • Char and Int are different types. Kotlin never converts between them silently. c.code goes from Char to Int, and toChar() goes back. Without the final conversion the function wouldn't match its return type.
    • The result is always a valid letter. Because the only value left is the code of one lowercase letter, between 97 and 122, toChar() loses nothing.
    • No fallback return is needed. Unlike the loop-and-return solutions, this one ends with a single return that always runs.

    Complexity

    Time: O(n). One pass over s and one over t, each step a single XOR.

    Space: O(1). The function keeps one integer and a loop variable, whatever the length of the strings.

    Edge cases and common mistakes

    • Empty s. Only the one letter of t is folded in, so result equals its code and "y" returns 'y'.
    • Duplicate letters. s = "aab" and t = "baab" returns 'b': both a pairs cancel, as do two of the three b letters.
    • Skipping one of the loops. XOR-ing only t leaves the XOR of all the letters of t, which is not the extra one unless s is empty. Both strings must be folded in.
    • Using the wrong operator. Plain and or or doesn't cancel equal numbers: 5 and 5 and 5 or 5 are both 5, not 0. XOR is the operation whose result for equal inputs is 0.
    • Forgetting .code or toChar(). The compiler reports a type mismatch between Char and Int.

    Testing

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