Find the Difference

Share

You are given two strings s and t. String t is generated by random shuffling string s and then adding 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 added to t.
Example 2
Input: s = "", t = "y"
Output: 'y'
Explanation: 'y' is the only character and is the added one.

Solution Approach

XOR all characters in both s and t together. Characters that appear in both strings cancel out (c ^ c = 0), leaving only the extra character added to t.

  • Initialize result = 0.
  • XOR every character in s into result.
  • XOR every character in t into result.
  • The remaining value is the added character.
Java
class Solution {
    public char findTheDifference(String s, String t) {
        char result = 0;
        for (char c : s.toCharArray()) result ^= c;
        for (char c : t.toCharArray()) result ^= c;
        return result;
    }
}
Complexity Analysis:

Time complexity: O(n). One pass through each string.
Space complexity: O(1). Constant extra space.