Find the Difference

Description

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.

Constraints

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Solution

There is actually a neat trick you can use for this particular problem which might not be super obvious if you lack knowledge about char codes (or runes as they are aliased in Go) and bitwise operations. More specifically the XOR operator. It is enabled by the fact that t and s consist of the exact same letters except for a the single one added to t, as well as the last constraint:

s and t consist of lowercase English letters.

Firstly, there are tons of things to learn about char codes though knowing that characters or symbols (read: letters) has a special number assigned to them is enough for this exercise.

Secondly, the way the XOR bitwise operator works is that for every position where the bit is flipped on (or 1) for only one of the operands it keeps it on. For the other two combinations it results in 0. Basically, if two bits are the same (i.e. both are 1 or both are 0) applying XOR will result in 0.

The following is the bit representations for the operation 24 ^ 17 visualised.

A visualisation says more than a 1111101000 words.

Notice how the bit in the fourth position for both 24 and 17 is 1 and after XOR is applied it becomes 0? So in the case of 97 ^ 97 (char code for a) all bits would result in 0. We can (ab)use this fact to write a really clean solution to this problem:

func findTheDifference(s string, t string) byte {
  var sum rune

  for _, c := range s + t {
    sum ^= c
  }

  return byte(sum)
}

If there’s a more optimal way of solving this problem then I would very much like to know!

Happy coding!