389 Find the Difference - Easy

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 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.

Problem Analysis:

• Let n be the length of the longer string between s and t.
• Constructing the counters (Counter(s) and Counter(t)) takes O(n) time and space.
• Calculating the difference (Counter(t) - Counter(s)) also takes O(n) time and space.
• Accessing the keys of the resulting counter and returning the first key takes constant time, so it's O(1).
• Therefore, the overall time and space complexity is O(n).

Solutions:

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        counter1 = Counter(s)
        counter2 = Counter(t)
        return [x for x in (Counter(t) - Counter(s)).keys()][0]
        # res = list(Counter(t) - Counter(s)).keys())
        # return res[0]

Similar Questions