Find the Difference

Difficulty: Easy | Acceptance: 60.30% | Paid: No Topics: Hash Table, String, Bit Manipulation, Sorting

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.

• Examples
• Constraints
• Approach 1: Hash Map (Frequency Count)
• Approach 2: Sorting
• Approach 3: Bit Manipulation (XOR)
• Approach 4: Summation

Examples

Example 1:

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

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.

Hash Map (Frequency Count)

Intuition We can count the frequency of each character in string s and then decrement the count while iterating through string t. The character that causes the count to drop below zero (or is missing from the map) is the added letter.

Steps

• Initialize an array or hash map of size 26 (for lowercase English letters) with zeros.
• Iterate through string s and increment the count for each character.
• Iterate through string t and decrement the count for each character.
• If the count for a character becomes negative, return that character immediately.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        for ch in t:
            cnt[ord(ch) - ord('a')] -= 1
            if cnt[ord(ch) - ord('a')] < 0:
                return ch
        return ''

Complexity

• Time: O(n)
• Space: O(1)
• Notes: We use a fixed-size array of 26 integers, so space complexity is constant regardless of input size.

Sorting

Intuition If we sort both strings, the characters will be in order. The extra character in t will either be the first character that doesn’t match s, or it will be the very last character of t if all previous characters match.

Steps

• Convert strings to character arrays (if necessary) and sort them.
• Iterate through the length of the shorter string s.
• If characters at index i differ between s and t, return the character from t.
• If the loop completes without finding a difference, return the last character of t.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        sorted_s = sorted(s)
        sorted_t = sorted(t)
        for i in range(len(s)):
            if sorted_s[i] != sorted_t[i]:
                return sorted_t[i]
        return sorted_t[-1]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Sorting dominates the time complexity. In languages where strings are immutable, converting to arrays requires O(n) space.

Bit Manipulation (XOR)

Intuition The XOR operation has a property that a ^ a = 0 and a ^ 0 = a. If we XOR all characters from both strings together, the characters appearing in both s and t will cancel each other out (result in 0). The result will be the ASCII value of the extra character.

Steps

• Initialize a variable res to 0.
• Iterate through string s and XOR each character’s ASCII value with res.
• Iterate through string t and XOR each character’s ASCII value with res.
• Convert the final integer value of res back to a character and return it.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the most optimal approach in terms of space and operation count, as it only requires a single integer variable.

Summation

Intuition Since t contains all characters of s plus one extra, the difference between the sum of ASCII values of characters in t and the sum of ASCII values of characters in s will be the ASCII value of the added character.

Steps

• Calculate the sum of ASCII values of all characters in s.
• Calculate the sum of ASCII values of all characters in t.
• Subtract the sum of s from the sum of t.
• Convert the resulting difference to a character and return it.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Similar to XOR, this uses O(1) space. However, in extreme cases with very long strings, the sum could theoretically overflow standard integer types, though with the constraint t.length <= 1001, this is not an issue for 32-bit integers.