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

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

        t_freq = {}
        for i in t:
            t_freq[i] = t_freq.get(i, 0) + 1
        for i in s:
            if i in t_freq.keys():
                t_freq[i] -= 1
                if t_freq[i] == -1:
                    return i
            else:
                return i
        for k, v in t_freq.items():
            if v == 1:
                return k
