Problem Explanation

Given two strings s and t, we want to find out the letter that was added in t. String t is created by shuffling string s and adding an extra letter in a random position. Both strings contain only lowercase letters.

Walk Through an Example

For example, if s = "abcd" and t = "abcde", the letter 'e' was added in t.

Approach Explanation

The problem can be solved using XOR ('^') operation in bit manipulation. The XOR operation can return a unique result given two inputs. If we take XOR of zero and a bit, it returns that bit

1
2
3  0 ^ 1 = 1
4  0 ^ 0 = 0

If we take XOR of two same bits, it returns 0

1
2
3  1 ^ 1 = 0
4  0 ^ 0 = 0

So if we take XOR of all the bits together, we get the unique bit, which is the letter added in 't'.

ASCII Illustration

1
2
3String s = "abcd"
4
5    a   b   c   d    
6    ∆   ∆   ∆   ∆  
7 1101 1110 1100 1101 => XOR operation on all bits of s
8
9
10String t = "abcde" 
11
12   a    b   c   d   e
13   ∆   ∆   ∆  ∆   ∆
14 1101 1110 1100 1101 1100 => XOR operation on all bits of t
15
16XOR operation on all bits of t and s = added letter 'e'

Solutions

Now, let's look at how to implement this solution in various programming languages.

Python Solution

1
2 python
3class Solution:
4    def findTheDifference(self, s: str, t: str) -> str:
5        ans = 0
6        # XOR operation on all characters in string s
7        for c in s:
8            ans ^= ord(c)
9        # XOR operation on all characters in string t
10        for c in t:
11            ans ^= ord(c)
12        # return the added character.
13        return chr(ans)

Java Solution

1
2 java
3class Solution {
4    public char findTheDifference(String s, String t) {
5        char ans = 0;
6        // XOR operation on all characters in string s
7        for (char c : s.toCharArray()) {
8            ans ^= c;
9        }
10        // XOR operation on all characters in string t
11        for (char c : t.toCharArray()) {
12            ans ^= c;
13        }
14        // return the added character
15        return ans;
16    }
17}

Javascript Solution

1
2javascript
3var findTheDifference = function(s, t) {
4    let ans = 0;
5    // XOR operation on all characters in string s
6    for (let i = 0; i < s.length; i++) {
7        ans ^= s.charCodeAt(i);
8    }
9    // XOR operation on all characters in string t
10    for (let i = 0; i < t.length; i++) {
11        ans ^= t.charCodeAt(i);
12    }
13    // return the added character
14    return String.fromCharCode(ans);
15};

C++ Solution

1
2 C++
3class Solution {
4public:
5    char findTheDifference(string s, string t) {
6        char ans = 0;
7        // XOR operation on all characters in string s
8        for (char c : s){
9            ans ^= c;
10        }
11        // XOR operation on all characters in string t
12        for (char c : t) {
13            ans ^= c;
14        }
15        // return the added character
16        return ans;
17    }
18};

C# Solution

1
2 C#
3public class Solution {
4    public char FindTheDifference(string s, string t) {
5        char ans = (char)0;
6        // XOR operation on all characters in string s
7        for (int i = 0; i < s.Length; i++) {
8            ans ^= s[i];
9        }
10        // XOR operation on all characters in string t
11        for (int i = 0; i < t.Length; i++) {
12            ans ^= t[i];
13        }
14        // return the added character
15        return ans;
16    }
17}

Final Thoughts

In each solution, the XOR operation helps to safely ignore all the characters that are common in both strings and leaves behind the character that was added in t. Thus the function returns the character that was added in string t.The mentioned approach makes use of bit manipulation, which is efficient but might not be straightforward for everyone. Alternatively, another solution could be to use a hash table or dictionary. Hashing works by assigning each unique character to a unique key in a table.

The dictionary-based solution would work as follows:

• Initialize an empty dictionary.
• Iterate through string 's', for each character 'c', add it to the dictionary. If 'c' already exists in the dictionary, increment its count.
• Iterate through string 't', for each character 'c', check if it is in the dictionary. If it is, decrease its count; if it's not, 'c' is the character that was added.
• Return the character added in 't'.

Here are the implementations of the dictionary-based solution:

Python Solution

1
2 python
3from collections import defaultdict
4
5def findTheDifference(s: str, t: str) -> str:
6      letters = defaultdict(int)
7      # count the letters in s
8      for c in s:
9         letters[c] += 1
10      # decrease the count of the letters found in t
11      for c in t:
12         if letters[c] == 0:
13            return c
14         letters[c] -= 1
15

Java Solution

1
2 java
3import java.util.*;
4
5public class Main {
6    public static char findTheDifference(String s, String t) {
7        int[] alphabet = new int[26];
8        for(char c : s.toCharArray()){
9            alphabet[c - 'a']++;
10        }
11
12        for(char c : t.toCharArray()){
13            if(--alphabet[c - 'a'] < 0){
14                return c;
15            }
16        }
17        return 0;
18    }
19}

JavaScript Solution

1
2 javascript
3var findTheDifference = function(s, t) {
4    let charCount = {};
5    for (let i=0; i < s.length; i++){
6        charCount[s[i]] = charCount[s[i]]+1 || 1;
7    }
8
9    for (let i=0; i < t.length; i++){
10        if (!charCount[t[i]]) return t[i];
11        charCount[t[i]] -= 1;
12    }
13};

These solutions also provide an efficient way to find the additional character. They are easier to understand but require more space (for storing the dictionary) compared to the XOR operation.