Find the Difference

easy string hash map bit manipulation

Problem

Strings s and t are anagrams except t has exactly one extra letter inserted at a random position. Return that extra letter.

Inputs = "abcd", t = "abcde"

Output"e"

'e' is the character that appears in t but not in s.

def find_the_difference(s, t):
    x = 0
    for c in s: x ^= ord(c)
    for c in t: x ^= ord(c)
    return chr(x)

function findTheDifference(s, t) {
  let x = 0;
  for (const c of s) x ^= c.charCodeAt(0);
  for (const c of t) x ^= c.charCodeAt(0);
  return String.fromCharCode(x);
}

class Solution {
    public char findTheDifference(String s, String t) {
        int x = 0;
        for (char c : s.toCharArray()) x ^= c;
        for (char c : t.toCharArray()) x ^= c;
        return (char) x;
    }
}

char findTheDifference(string s, string t) {
    int x = 0;
    for (char c : s) x ^= c;
    for (char c : t) x ^= c;
    return (char) x;
}

Explanation

Both strings contain the same letters except t has one extra. The slick way to find that extra letter is to XOR every character of both strings together. The two magic facts behind XOR are x ^ x = 0 and x ^ 0 = x.

Because every shared character appears once in s and once in t, it gets XOR-ed twice and cancels out to zero. The one letter that appears only in t has no partner to cancel with, so it is the only thing left in our running value x.

We XOR the numeric code of each character into x, then turn the surviving number back into a character at the end.

Example: s = "abcd", t = "abcde". The a, b, c, d each appear twice and cancel, leaving only the code of 'e'. Converting that back gives "e".

This uses just one integer of memory and a single pass over both strings, with no counting tables needed.

Time: O(n) Space: O(1)