"""
389. Find the Difference
https://leetcode.com/problems/find-the-difference/

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:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Input: s = "", t = "y"
Output: "y"
""""

# Runtime: 28ms (94.75%)
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:

        from collections import Counter

        combined = s + t

        hash_table = Counter(combined)

        return list(filter(lambda x: x[1] % 2 == 1, hash_table.items()))[0][0]
