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.

#
# [389] Find the Difference
#
# https://leetcode.com/problems/find-the-difference
#
# Easy (51.49%)
# Total Accepted:    65096
# Total Submissions: 126396
# Testcase Example:  '"abcd"\n"abcde"'
#
 
# Example:
# 
# Input:
# s = "abcd"
# t = "abcde"
# 
# Output:
# e
# 
# Explanation:
# 'e' is the letter that was added.
# 
#
from collections import defaultdict
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """

        s_map = defaultdict(int)
        t_map = defaultdict(int)
        for char in s:
            s_map[char] += 1
        for char in t:
            t_map[char] += 1

        for key, val in t_map.items():
            if val != s_map.get(key, 0):
                return key
        return ""


from collections import Counter
class Solution(object):
    def findTheDifference(self, s, t):
        return list((Counter(t) - Counter(s)))[0]

class Solution(object):
    def findTheDifference(self, s, t):
        s, t = sorted(s), sorted(t)
        return t[-1] if s == t[:-1] else [x[1] for x in zip(s, t) if x[0] != x[1]][0]