389. Find the Difference - Explanation

Problem Link

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.

Example 1:

Input: s = "abcd", t = "abcde"

Output: "e"

Explanation: 'e' is the letter that was added.

Example 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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Two Hash Maps

Intuition

String t is formed by shuffling string s and adding one extra character. By counting the frequency of each character in both strings, the added character will have a higher count in t than in s. We can compare these counts to find the difference.

Algorithm

1. Create two count arrays of size 26 for characters in s and t.
2. Count the frequency of each character in both strings.
3. Compare the counts. The character where countT[i] > countS[i] is the answer.
4. Return that character.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        count_s, count_t = Counter(s), Counter(t)
        for c in count_t:
            if c not in count_s or count_s[c] < count_t[c]:
                return c

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

---

2. One Hash Map

Intuition

Instead of using two separate count arrays, we can use a single array. First count all characters from t, then subtract counts for characters in s. The character left with count 1 is the added character.

Algorithm

1. Create a count array of size 26.
2. Increment counts for each character in t.
3. Decrement counts for each character in s.
4. Find and return the character with count equal to 1.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        count = Counter(t)
        for c in s:
            count[c] -= 1
        for c in count:
            if count[c] == 1:
                return c

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

---

3. Sorting

Intuition

After sorting both strings, corresponding characters at each position should match since t is a shuffled version of s plus one character. The first position where they differ reveals the added character. If all positions match, the added character is at the end of t.

Algorithm

1. Sort both strings s and t.
2. Compare characters at each position.
3. Return the first character in t that differs from the corresponding character in s.
4. If all characters match, return the last character of t.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s, t = sorted(s), sorted(t)
        for c1, c2 in zip(s, t):
            if c1 != c2:
                return c2
        return t[-1]

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

4. Difference Between ASCII Values

Intuition

Each character has an ASCII value. If we sum the ASCII values of all characters in t and subtract the sum of ASCII values in s, the result equals the ASCII value of the added character. This works because all matching characters cancel out.

Algorithm

1. Compute the sum of ASCII values for all characters in s.
2. Compute the sum of ASCII values for all characters in t.
3. Subtract sumS from sumT.
4. Convert the result to a character and return it.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        sum_s, sum_t = 0, 0
        for c in s:
            sum_s += ord(c)
        for c in t:
            sum_t += ord(c)
        return chr(sum_t - sum_s)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.

---

5. Difference Between ASCII Values (Optimal)

Intuition

We can optimize space by using a single variable instead of two separate sums. By subtracting ASCII values from s and adding ASCII values from t to the same variable, we compute the difference in one pass through both strings.

Algorithm

1. Initialize res = 0.
2. For each character in s, subtract its ASCII value from res.
3. For each character in t, add its ASCII value to res.
4. Convert res to a character and return it.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for c in s:
            res -= ord(c)
        for c in t:
            res += ord(c)
        return chr(res)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.

---

6. Bitwise XOR

Intuition

XOR has a useful property: a ^ a = 0 and a ^ 0 = a. If we XOR all characters from both strings together, each character that appears in both s and t will cancel out (XOR with itself gives 0). The only character remaining is the added one, since it appears an odd number of times total.

Algorithm

1. Initialize res = 0.
2. XOR res with each character's ASCII value in s.
3. XOR res with each character's ASCII value in t.
4. Convert res to a character and return it.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for c in s:
            res ^= ord(c)
        for c in t:
            res ^= ord(c)
        return chr(res)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.

---

Common Pitfalls

Forgetting to Handle Empty String s

When s is an empty string, t contains exactly one character (the added one). Solutions that iterate through s first or rely on finding a mismatch between sorted strings must handle this edge case. The XOR and sum-based approaches naturally handle this since XORing or summing over an empty string contributes nothing.

Comparing Characters Instead of Counts

A common mistake is to iterate through both strings and return the first character in t that does not appear in s. This fails when the added character is a duplicate of an existing character. For example, if s = "a" and t = "aa", the added character is 'a', but a naive check would miss it since 'a' already exists in s.