Problem

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.

Examples

Example 1:

1
2
3

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

1
2

Input: s = "", t = "y"
Output: "y"

Constraints

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

Solution

Method 1 - Sorting

Just sort the array, and find the first different letter. Here is the approach:

  • Convert both strings s and t into character arrays.
  • Sort both arrays.
  • Compare characters sequentially; the first mismatch is the additional character in t.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {

	public char findTheDifference(String s, String t) {
		int n = s.length();

		// Convert strings to character arrays and sort them
		char[] sArray = s.toCharArray();
		char[] tArray = t.toCharArray();

		Arrays.sort(sArray);
		Arrays.sort(tArray);

		// Compare characters in the sorted arrays
		for (int i = 0; i < n; i++) {
			if (sArray[i] != tArray[i]) {
				return tArray[i];
			}
		}

		// If no mismatch found in the first n characters, return the last character of t
		return tArray[n];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        # Convert strings to lists of characters and sort them
        s_array: List[str] = sorted(s)
        t_array: List[str] = sorted(t)

        # Compare characters in the sorted arrays
        for i in range(len(s)):
            if s_array[i] != t_array[i]:
                return t_array[i]

        # If no mismatch found in the first n characters, return the last character of t
        return t_array[len(s)]

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

Method 2 - Using map

Here is another approach:

  • Use a hashmap to count occurrences of each character in s.
  • Decrease the count for each character in t and find the character with a negative count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {

	public char findTheDifference(String s, String t) {
		HashMap<Character, Integer> map = new HashMap<>();

		for (char c: s.toCharArray()) {
			map.put(c, map.getOrDefault(c, 0) + 1);
		}

		for (char c: t.toCharArray()) {
			map.put(c, map.getOrDefault(c, 0) - 1);

			if (map.get(c)<0) {
				return c;
			}
		}

		return '-1';
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        count_map = defaultdict(int)
        
        # Increase count for each character in s
        for char in s:
            count_map[char] += 1

        # Decrease count for each character in t
        for char in t:
            count_map[char] -= 1
            if count_map[char] < 0:
                return char

        return ''

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Use Xor

Here is the approach:

  • Use XOR to cancel out corresponding characters in s and t. The remaining character is the added character.
  • XOR of a character with itself is zero, and XOR with zero is the character itself.

Code

1
2
3
4
5
6
7
8
9

public char findTheDifference(String s, String t) {
		int n = t.length();
		char c = t.charAt(n - 1);
		for (int i = 0; i < n - 1; ++i) {
			c ^= s.charAt(i);
			c ^= t.charAt(i);
		}
		return c;
}
1
2
3
4
5
6

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        ans: str = t[-1]
        for i in range(len(t) - 1):
            ans = chr(ord(ans) ^ ord(s[i]) ^ ord(t[i]))
        return ans

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)