Start learning free

LESSON 399 OF 443 · BIT MANIPULATION

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

    SWIFT · BIT MANIPULATION

    Find The Difference in Swift, explained

    Problem overview

    The method findTheDifference receives two strings. The string t is s shuffled with one extra letter inserted, and the method returns that letter as a Character.

    For s = "abcd" and t = "abcde" the answer is "e". 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. A dictionary of counts is linear in time as well, but this lesson's goal is to get rid of the dictionary and keep a single number.

    Approach: XOR cancels pairs

    The XOR operation, written ^ in Swift, combines two integers bit by bit: a result bit is 1 when exactly one of the two input bits is 1. It has three properties that matter here:

    • x ^ x = 0: a number XORed with itself cancels out.
    • x ^ 0 = x: XOR with 0 changes nothing.
    • The order doesn't matter, so the numbers can be combined in any sequence.

    Every letter has a numeric code. Start with 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 the two cancel to 0, wherever they sit and however many other letters lie between them. The extra letter has no partner. What remains is its code.

    For example, with s = "ae" and t = "aea", the codes are 97 for a and 101 for e. The XOR of 97, 101, 97, 101, 97 is 97, the code of a. Two as cancel, the two es cancel, and one a is left.

    This works even when the extra letter duplicates a letter from s, because cancelling happens per copy: three as in total leave one a after one pair cancels. The solution keeps one small number, so the extra space is constant.

    Step by step

    1. Declare an accumulator. var result: UInt8 = 0 holds one byte. A byte is enough for a lowercase letter's code, and UInt8 supports ^.
    2. Loop over the bytes of s. s.utf8 is a view of the string as its UTF-8 bytes, so for c in s.utf8 gives UInt8 values, not Characters.
    3. XOR each byte into result with result ^= c.
    4. Loop over the bytes of t in the same way.
    5. XOR those bytes in too. After this loop, every letter that occurs in both strings has been combined twice and cancelled, and only the extra letter is left in result.
    6. Turn the byte back into a character. UnicodeScalar(result) makes a Unicode scalar from the byte, and Character(...) wraps it as the return type requires.

    The solution in Swift

    class Solution {
    func findTheDifference(_ s: String, _ t: String) -> Character {
        var result: UInt8 = 0
        for c in s.utf8 {
            result ^= c
        }
        for c in t.utf8 {
            result ^= c
        }
        return Character(UnicodeScalar(result))
    }
}

    The Swift details worth a closer look:

    • utf8 is a view, not a copy. It walks the string's bytes without building an array. For the lowercase letters in this lesson each character is exactly one byte, equal to its ASCII code: Array("abc".utf8) is [97, 98, 99].
    • Non-ASCII text is different. A character such as é takes two bytes, and Array("é".utf8) is [195, 169]. The bytes would still cancel in pairs, but the one-byte result at the end could no longer name the character. The lesson's input is limited to lowercase English letters, so this is safe here.
    • ^= is XOR-and-assign. result ^= c means result = result ^ c. Both sides are UInt8, so no conversion is needed.
    • The UInt8 initializer can't fail. Every byte value is a valid Unicode scalar, so UnicodeScalar(result) returns a plain value. The version that takes an Int returns an optional instead, because not every integer is a valid scalar: UnicodeScalar(Int(97)) gives Optional("a"). That is why the accumulator is a UInt8 and not an Int.
    • No fallback return is needed. Unlike the loop-and-return solutions, this method always reaches its last line.
    • No overflow can happen. XOR never produces a value outside the range of its operands' type, so there is no arithmetic trap to worry about.

    Complexity

    Time: O(n). The first loop runs n - 1 times and the second runs n times, with one XOR in each pass.

    Space: O(1). The only state is the byte result and the loop variables. The utf8 views don't copy the strings.

    Edge cases and common mistakes

    • Empty s. The first loop does nothing, and the second XORs the single byte of t into 0. Since x ^ 0 = x, the result is that byte, so "y" comes back for t = "y".
    • The extra letter repeats a letter of s. s = "aab" and t = "abaa" gives "a": three as and two bs are XORed, the pairs cancel, and one a remains.
    • Using + instead of ^. Addition doesn't cancel anything. Subtracting would work in principle, but UInt8 arithmetic traps when it overflows, so XOR is the safer tool here.
    • Accumulating in an Int. That works for the XOR itself, but the last step then needs an Int-to-scalar conversion that returns an optional.
    • Looping over s and t as strings. A loop over the string gives Character values, and ^ isn't defined for them. Loop over utf8.

    Testing

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