## Similar Problems

Similar Problems not available

# Find The Difference - Leetcode Solution

LeetCode: Find The Difference Leetcode Solution

Difficulty: Easy

Topics: string hash-table sorting bit-manipulation

Problem:

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:

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

Solution:

To solve this problem, we can use a hash map to store the frequency of each character in string t and string s. Then we can easily find the letter that was added to t by comparing the frequency of each character in the two strings.

Here's the detailed explanation of the solution:

- Create a hash map
`freq`

to store the frequency of each character in string t. - Loop through each character
`ch`

in string t and update its frequency in`freq`

. - Loop through each character
`ch`

in string s and update its frequency in`freq`

. - Loop through each character
`ch`

in`freq`

and find the character with frequency difference of 1 and return it.

Here's the implementation of the solution:

```
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
freq = {}
for ch in t:
freq[ch] = freq.get(ch, 0) + 1
for ch in s:
freq[ch] -= 1
for ch in freq:
if freq[ch] == 1:
return ch
```

Time Complexity:

The time complexity of the solution is O(n), where n is the length of string t. We are looping through string t and s once, and the hash map operations take constant time.

Space Complexity:

The space complexity of the solution is O(1). We are using a hash map to store the frequency of characters in string t and s, which has at most 26 keys in it. So the space complexity is constant.

## Find The Difference Solution Code

`1`