Problem of the week - Anagram

Ashish srivastava Ashish Srivastava | @ashishsrtechie | 21 Sep, 2015


Imagine you are about to receive a call from a Facebook interviewer and you are nervously biting your nails, hoping for things to go well. The phone rings, and after a brief introduction and small talk, Seregey throws the following question your way -

Write a function to check whether two strings are anagrams of each other or not. An anagram is another string that contains the same characters in a different order. For example, “tip” and “pit” are anagrams of each other.

Approach 1 :

First, it is extremely important to understand what exactly an anagram is. Here is the wiki link which explains it in (too much) detail. https://en.wikipedia.org/wiki/Anagram

Let’s get started !

Hint: Does sorting help?

Sure it does! Once the characters in the input strings are sorted, a simple comparison would tell us if they are anagrams of each other or not.


Implementation:

      /* Sorting two input strings and comparing them to find out if they are anagrams of each other. */
        public boolean isAnagram(String input1, String input2) {
          char[] input1Chars = input1.toCharArray();
          char[] input2Chars = input2.toCharArray();
          // Inbuilt sorting
          Arrays.sort(input1Chars);
          Arrays.sort(input2Chars);
          String sorted1 = new String(input1Chars);
          String sorted2 =  new String(input2Chars);
          if(sorted1.equals(sorted2)) {
              return true;
          }
          return false;
       }
  

However, an efficient coding practice is to avoid complex processing whenever possible. A simple if condition in the above solution can make it more efficient and avoid unnecessary processing for basic cases.

 
            /* Sorting two input strings and comparing them to find out if they are anagrams of each other. */  
            public boolean isAnagram(String input1, String input2) {
             // Additional condition to avoid unnecessary processing
            if(input1 == null || input2 == null || (input1.length() != input2.length()))
               {
                   return false;
               }
              char[] input1Chars = input1.toCharArray();
              char[] input2Chars = input2.toCharArray();
              Arrays.sort(input1Chars);
              Arrays.sort(input2Chars);
              String sorted1 = new String(input1Chars);
              String sorted2 =  new String(input2Chars);
              if(sorted1.equals(sorted2)) {
                  return true;
              }
               return false;
            }
        

Time Complexity :

In the above code, all the time needed is for the sorting to complete. Hence, the complexity depends on the type of sorting used. According to Oracle's documentation, Array.sort() is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(char%5B%5D) The above solution is good. Let us see if the implementation can be made even more efficient. What if there is an additional constraint that the input string is made of only 8 bits and hence, there can be only 256 possible characters?

Hint: Array to store character counts

  1. Create two count arrays of size 256 for each of the input strings.
  2. Iterate through both the arrays and increment the count of characters in the corresponding arrays. If both the arrays are the same, then they are anagrams of each other.

Approach 2

 
              /* Storing the frequency of the characters in count arrays, comparing them to find out if they are anagrams of each other or not.*/  
              public boolean isAnagram(String input1, String input2)
              {
                  if(input1 == null || input2 == null || (input1.length() != input2.length()))
                        {
                           return false;
                        }
                        char [] str1Array = input1.toCharArray();
                        char [] str2Array = input2.toCharArray();
                          
                                  
                         int [] count1 =new int[256];
                         int [] count2 =new int[256];
                         int i;
                         for (i = 0; i < str1Array.length;  i++)
                            {
                             count1[str1Array[i]]++;
                             count2[str2Array[i]]++;
                             }
                      
                         // Compare count arrays
                         for (i = 0; i < 256; i++)
                             if (count1[i] != count2[i])
                             {
                              return false;
                             }
                         return true;
              }
          

Time Complexity:

Since we only traverse the input string once, the complexity is O(n). Now what if you want to further reduce the space complexity? The above solution can be rewritten with just one count array! While traversing the second input string, decrement the characters from the first count array. Another constraint which could further reduce the space complexity can be that if the input string is made of only English alphabets, then we can initialize the array to a size of just 52 and the index can be found by using the formula Character.getNumericValue(str2Array[i]) - 65; for upper case letters.

To solve such questions and prepare for coding interviews - log on to firecode.io

Think you have more efficient or better solution? share it in the comments!