Find the Difference Python

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

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

Output:
e

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

Using sorting

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        x = sorted(s)
        y = sorted(t)
        i = 0
        while i < len(x):
            if x[i] != y[i]:
                return y[i]
            i+=1
        return y[i]

Time Complexity : O(nlogn)

Space Complexity : O(1) sorting in python takes inplace so O(1)

Using Hashmap :

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        counter_s = Counter(s)
        for ch in t:
            if ch not in counter_s or counter_s[ch] == 0:
                return ch
            else:
                counter_s[ch] -=1

Time Complexity : O(n)

Space Complexity : O(1)

Using Bit manipulation :

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

Time Complexity : O(n)

Space complexity : O(1)