class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;

        // O(n+m), O(K)~=O(1) because K<=26 characters
        Map<Character, Integer> map = new HashMap<>();
        
        for(char ch : s.toCharArray())
        {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        for(char ch : t.toCharArray())
        {
            if(!map.containsKey(ch)) 
                return false;
            
            int freq = map.get(ch);
            freq--;

            if(freq == 0)
                map.remove(ch);          // remove when zero
            else
                map.put(ch, freq);       // update otherwise
        }
        if(map.size() == 0)
            return true;
        // if(map.values().stream().allMatch(value -> value == 0))
            // return true;
        return false;
    }
    
    // Time: O(n log n) Space: O(n)
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;

        char[] arr1 = s.toCharArray();
        Arrays.sort(arr1);

        char[] arr2 = t.toCharArray();
        Arrays.sort(arr2);

        int i=0,j=0;
        while(i<arr1.length && j<arr2.length)
        {
            if(arr1[i] != arr2[i])
                return false;
            
            i++;
            j++;
        }
        return true;
    }
}