package strings;


//Two strings  and  are called anagrams if they consist same characters, but may be in different orders. So the list of anagrams of  is .
//
//Given two strings, print Anagrams if they are anagrams, print Not Anagrams if they are not. The strings may consist at most  English characters; the comparison should NOT be case sensitive.
//
//This exercise will verify that you can sort the characters of a string, or compare frequencies of characters.
//
//
//
//Sample Input 0
//
//anagram
//margana

//Sample Output 0
//
//Anagrams



//Sample Input 1
//
//anagramm
//marganaa

//Sample Output 1:
//
//Not Anagrams





import java.io.*;
import java.util.*;

public class Solution {
	
	 //My hash map is initialized based on the fact that this is only using English characters as is stated in the problem constraints

	//Overall time complexity: O(n)
	//Overall space complexity: O(1)

	static boolean isAnagram(String a, String b)
  {
      boolean anagram = true;
      Character[] charSet =   {'A','B','C','D','E',
                            'F','G','H','I','J',
                            'K','L','M','N','O',
                            'P','Q','R','S','T',
                            'U','V','W','X','Y','Z'};
      HashMap<Character,Integer> ALetterFrequency = new HashMap<Character,Integer>();
      HashMap<Character,Integer> BLetterFrequency = new HashMap<Character,Integer>();
      intializeHash(ALetterFrequency, charSet);       //O(n)
      intializeHash(BLetterFrequency, charSet);       //O(n)
      a = a.toUpperCase(); //O(n)
      b = b.toUpperCase(); //O(n)
      
      //Originally I took a different approach to this problem because I was using substring and it 
      // runs in O(n) which would make my algorithm run in O(n^2) with constant space, but then I
      // remembered that charAt() runs in constant time so utilizing that function I was able to
      // have a time complexity of O(n) and space complexity of O(1)
      
      for(int i = 0;i <a.length();i++)  //O(n)
      {
    	  Character letter = a.charAt(i);   //O(1)
          Integer frequency = ALetterFrequency.get(letter);
          ALetterFrequency.put(letter,++frequency);
      }
      for(int i = 0;i <b.length();i++)  //O(n)
      {
          Character letter = b.charAt(i);   //O(1)
          Integer frequency = BLetterFrequency.get(letter);
          BLetterFrequency.put(letter,++frequency);
      }
      
      
      //Compare Hash
      for(Character letter : charSet)
      {
          if(!ALetterFrequency.get(letter).equals(BLetterFrequency.get(letter)))
          {
              anagram = false;
          }
      }
      
      return anagram;
  }
  static void intializeHash(HashMap hash, Character[] set)
  {
      for(Character letter : set)
     {
          hash.put(letter,0);
     }
          
  }
  static Character[] toCharacterArray(char[] cArray)
  {
      Character[] CArray = new Character[cArray.length];
      for(int i =0; i<cArray.length;i++)
      {
          CArray[i] = (Character) cArray[i];
      }
      return CArray;
  }
	    
	    public static void main(String[] args) {
	        
	        //Scanner scan = new Scanner(System.in);
	        String a = "anagramm";
	        String b = "marganaa";
	        //scan.close();
	        boolean ret = isAnagram(a, b);
	        System.out.println( (ret) ? "Anagrams" : "Not Anagrams" );
	    }

}