# 389. Find the Difference

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.

Approach 1:

*Using map*

Here we traverse “s” and we store the count of each character in a map.

Then we traverse “t” and for each character we traverse if that character is in the map , that is that character was found to present in “s” also , then we decrement the count of that character from the map. The main point to note here is , the newly added character to s will be one that is not present in “s” or whose count in the map is 0.

`class Solution:`

def findTheDifference(self, s: str, t: str) -> str:

dict_=dict()

for i in s:

if i in dict_:

dict_[i]+=1

else:

dict_[i]=1

for i in t:

if(i not in dict_ or dict_[i]==0):

return i

else:

dict_[i]-=1

*Time : O(N)*

*Space: O(N)*

Approach 2:

*Using sorting*

`class Solution:`

def findTheDifference(self, s: str, t: str) -> str:

s=sorted(s)

t=sorted(t)

for i in range(len(s)):

if s[i]!=t[i]:

return t[i]

return t[-1]

*Time : O(nlgn)*

*Space: O(1)*

Approach 3:

*More optimized solution in terms of time and space*

`class Solution:`

def findTheDifference(self, s: str, t: str) -> str:

tot=0

for i in range(len(t)):

tot+=ord(t[i])

if(i<len(s)):

tot-=ord(s[i])

return(chr(tot))

#time =O(len(t))

#space = O(1)

*Time : O(N)*

*Space: O(1)*

Approach 4:

*Bit manipulation*

The newly added character can be obtained by xoring all the ascii values of a all the character.

`class Solution:`

def findTheDifference(self, s: str, t: str) -> str:

xor_=0

for i in range(len(s)):

xor_^=ord(s[i])^ord(t[i])

return(chr(xor_^ord(t[-1])))

*Time : O(N)*

*Space: O(1)*