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 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

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

Constraints:

• 0 <= s.length <= 1000

• t.length == s.length + 1

• s and t consist of lowercase English letters.

import java.util.Arrays;
import java.util.Map;

import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;

public class LC_389_FindTheDifference {
    /**
     * Approach - 1 - Using HashMap
     *
     * Used Stream API to build the HashMap
     *
     * Time Complexity - O(n) + O(m)
     * Space Complexity - O(n)
     * where n - length of s
     *       m - length of t
     *
     * @param s - String
     * @param t - String
     * @return char
     */
    public char findTheDifference_UsingHashMap(String s, String t) {
        // Used Stream to generate frequency of each character in the string adn store it in the map
        Map<Character, Long> map = Arrays.stream(s.split(""))
                .collect(groupingBy(str -> str.charAt(0), counting()));

        for(char ch : t.toCharArray()){
            if(!map.containsKey(ch) || map.get(ch)<=0){
                return ch;
            }
            map.put(ch, map.get(ch)-1);
        }

        return '#';
    }

    /**
     * Approach - 2 - Simple addition
     * 
     * Since all characters in String 't' will be present in string 's'
     * Add all characters in string t and subtract characters in string s
     * 
     * Time Complexity - O(n) + O(m)
     * Space Complexity - O(1)
     * where n - length of s
     *       m - length of t
     * @param s - String
     * @param t - String
     * @return char
     */
    public char findTheDifference(String s, String t) {
        char result = 0;

        for(char ch : s.toCharArray()){
            result -= ch;
        }

        for(char ch : t.toCharArray()){
            result += ch;
        }

        return result;
    }

    public static void main(String[] args) {
        LC_389_FindTheDifference findDiff = new LC_389_FindTheDifference();

        // Approach - 1
        System.out.println("Approach - 1");
        System.out.println(findDiff.findTheDifference_UsingHashMap("a", "aa")); // 'a'
        System.out.println(findDiff.findTheDifference_UsingHashMap("aa", "aa")); // '#' - all characters are present
        System.out.println(findDiff.findTheDifference_UsingHashMap("abc", "aabc")); // 'c'
        System.out.println(findDiff.findTheDifference_UsingHashMap("abcd", "abcde")); //'e'

        // Approach - 2
        System.out.println("Approach - 2");
        System.out.println(findDiff.findTheDifference("a", "aa")); // 'a'
        System.out.println(findDiff.findTheDifference("aa", "aa")); // '#' - all characters are present
        System.out.println(findDiff.findTheDifference("abc", "aabc")); // 'c'
        System.out.println(findDiff.findTheDifference("abcd", "abcde")); //'e'
    }
}