389. Find the Difference - Explanation

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

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

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

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

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)

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

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.