Find the Difference

Bit ManipulationString

10 min

Problem Statement

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

Example 1:

Input: s = "abcd", t = "abcde"

Output: "e"

Explanation: 'e' is the letter that was added.

Solution (XOR)

This problem is a perfect application of the XOR bitwise operator. Since string t contains all characters of s plus one extra character, we can find the difference by XORing all character codes together.

The characters that are in both strings will cancel each other out (a ^ a = 0), leaving only the character code of the added letter.

Algorithm Steps

Initialize a character or integer variable result to 0.
Iterate through each character in string s and XOR its character code with result.
Iterate through each character in string t and XOR its character code with result.
The final value of result, when converted back to a character, is the added letter.

String `s`:

String `t`:

Current XOR Result: 00000000

Result as Char: '...'

Initialize result = 0

Find the Difference Solution


class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        result = 0
        for char in s:
            result ^= ord(char)
        for char in t:
            result ^= ord(char)
        return chr(result)