""" Find the difference - https://leetcode.com/problems/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(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        from collections import Counter
        c1 = Counter(s)
        c2 = Counter(t)
        for key in c2:
            if key not in c1 or c2[key] > c1[key]:
                return key