"""
Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.
"""
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        
        seen = dict()
        
        for i in s:
            seen[i] = seen.get(i, 0) + 1
        
        for j in t:
            if j not in seen:
                return j
            seen[j] -= 1
            if seen[j] == 0:
                del seen[j]
        
        return seen.keys()[0]
    
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        for ch in t:
            if (s+t).count(ch)%2:
                return ch;
            


