Find The Difference - Leetcode Solution

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.

1