// Valid Anagrams - https://leetcode.com/problems/valid-anagram/sou

class Solution {

    // Sort the underlying character arrays & compare
    // For anagrams they should be an exact match
    // Time Complexity: O(nlogn)
    // Space Complexity: O(n)
    // public boolean isAnagram(String s, String t) {
    //     if(s == null && t == null) {
    //         return true;
    //     }

    //     if(s == null || t == null) {
    //         return false;
    //     }

    //     if(s.length() != t.length()) {
    //         return false;
    //     }


    //     char[] sChars = s.toCharArray();
    //     char[] tChars = t.toCharArray();

    //     Arrays.sort(sChars);
    //     Arrays.sort(tChars);

    //     for(int i = 0; i < s.length(); i++) {
    //         if(sChars[i] != tChars[i]) {
    //             return false;
    //         }
    //     }

    //     return true;
    // }

    // Using HashMap to count characters in one of the strings
    // and using the other string to decrement counts in Hashmap
    // Time Complexity: O(n)
    // Space Complexity: O(k) 
    //   where k is number of unique characters in the string
    // LeetCode indicate above solution to be much better despite the complexity
    // public boolean isAnagram(String s, String t) {
    //     if(s == null && t == null) {
    //         return true;
    //     }

    //     if(s == null || t == null) {
    //         return false;
    //     }

    //     if(s.length() != t.length()) {
    //         return false;
    //     }

    //     Map count = new HashMap<>();

    //     for (int i = 0; i < s.length(); i++) {
    //         count.put(s.charAt(i), count.getOrDefault(s.charAt(i), 0) + 1);
    //     }

    //     for (int i = 0; i < t.length(); i++) {
    //         char c = t.charAt(i);
    //         if(!count.containsKey(c)) {
    //             return false;
    //         }

    //         int counter = count.get(c) - 1;
    //         if (counter < 0) {
    //             return false;
    //         }

    //         count.put(c, counter);
    //     } 

    //     for(Integer countValue: count.values()) {
    //         if (countValue != 0) {
    //             return false;
    //         }
    //     }

    //     return true;
    // }

    // Using Array to count characters 
    // Time Complexity: O(n)
    // Space Complexity: O(1) 
    // LeetCode indicate sorting solution to be much better despite the complexity
    public boolean isAnagram(String s, String t) {
        if(s == null && t == null) {
            return true;
        }

        if(s == null || t == null) {
            return false;
        }

        if(s.length() != t.length()) {
            return false;
        }

        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
            freq[t.charAt(i) - 'a']--;
        }

        for(int i = 0; i < freq.length; i++) {
            if(freq[i] != 0) {
                return false;
            }
        }

        return true;
    }
}