// Efficient : Time Complexity : O(n)
 
import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
        
    static boolean areAnagram(String s1, String s2) 
    { 
       if (s1.length() != s2.length()) 
            return false; 
  
        int[] count=new int[CHAR];
        for(int i=0;i<s1.length();i++){
            count[s1.charAt(i)]++;
            count[s2.charAt(i)]--;
        }
    
        for(int i=0;i<CHAR;i++){
            if(count[i]!=0)return false;
        }
        return true;
    }
  
    public static void main(String args[]) 
    { 
        String str1 = "abaac"; 
        String str2 = "aacba";  
        if (areAnagram(str1, str2)) 
            System.out.println("The two strings are" + " anagram of each other"); 
        else
            System.out.println("The two strings are not" + " anagram of each other"); 
    } 
} 
 
 

// Naive : Time Complexity : Θ(nlogn)
 
    static boolean areAnagram(String s1, String s2) 
    { 
       
        if (s1.length() != s2.length()) 
            return false; 
  
       char a1[]=s1.toCharArray();
        Arrays.sort(a1);
        s1=new String(a1);
        char a2[]=s2.toCharArray();
        Arrays.sort(a2);
        s2=new String(a2);
        
        return s1.equals(s2);
    } 

// SOLUTION 1 - MY (DISCOVERED) SOLUTION (RUNTIME - 104MS, 44.9 MB)
var isAnagram = function(s, t) {
    
    // set function to split, sort, and rejoin characters in a string
    const sortString = (str) => {
        return str.split("").sort().join("");
    }
    
    // regex removes any non-alphabet characters in the string and makes it lowercase
    s = s.replace(/[^\w]/g, '').toLowerCase()
    t = t.replace(/[^\w]/g, '').toLowerCase()

    // final comparison
    return sortString(s) === sortString(t)
  
  // ATTEMPT 1
  //     let anagram = []
    
  // return false is lengths don't match
  //     if (s.length !== t.length) return false;
  //     else {
  //         for (let i = 0; i < s.length; i++) {
  //             let arrT = t.split("")
  //             let newArrT;
  //             if (arrT.includes(s.charAt(i))) {
  //                 let index = arrT.indexOf(s.charAt(i));
  //                 console.log("s char: ", s.charAt(i));
  //                 console.log("index: ", index);

  //                 anagram.push(s.charAt(i))

  //                 console.log("splice: ", arrT.splice(index, 1))
  //                 arrT.splice(index, 0)

  //                 newArrT = arrT
  //                 console.log("newArr: ", newArrT)
  //             };
  //         };
  //     }
  //     console.log(anagram)
  //     return anagram.join("") === s;
}

// SOLTUION 2 - (BEST RUNTIME - 60MS)
var isAnagram = function(s, t) {
    const key = w => Object.entries([...w].reduce((a, c) => {
        if (!(c in a)) a[c] = 0;
        a[c] += 1;
      
        return a;
    }, {})).sort(([c1], [c2]) => c1.localeCompare(c2)).flat().join('');
  
    return key(s) === key(t);
};

// SOLUTION 3 - (RUNTIME - 72MS)
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false;
  
    let map = {};
  
    for(let item of s) {
        map[item] = map[item] + 1 || 1;
    }
    
    for(let item of t) {
        if(!map[item]) return false;
        else map[item]--;
    }
  
    return true;
};