Author: Ajay Iyengar

In this blog we are going to learn how to find if 2 given strings are anagrams of each other. We will be solving this problem without sorting the 2 strings and see if we can improve on the time complexity. I have a step by step explanation of finding if 2 strings are anagrams using a sorting technique here. If you are completely new to anagrams and would like know about solving this in Java using sorting, I would urge you read that first.

How can we solve this problem without sorting the strings ?

Let’s start with a simple example, an example which we saw in the previous blog about anagrams – “evil” and “vile” or “coronavirus” and “carnivorous”. These are anagrams since the characters in them are the same and they appear the same number of times, the characters are just rearranged.

They key here is that they appear the same number of times. This means the frequency of each character in the 2 strings is the same. In the string “evil”, each character, ‘e’, ‘v’, ‘i’ and ‘l’ appears once in the string “vile”.

The image below shows you the frequency of each character in the strings “coronavirus” and “carnivorous”

It is clear that each character in “coronavirus” has same frequency as characters in “carnivorous”. Can we use this frequency to figure out if they are anagrams ?

Finding out the frequency of each character in the string

Like the previous blog, we are going to remove any spaces and also going to convert all letters to lowercase. So let’s begin with some code.

public static boolean isAnagram(String first, String second) {

        char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();
        char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

        if (charactersOfFirst.length != charactersOfSecond.length) {
            return false;
        }

        //Code here for frequency check.

        return true;
    }

We have converted both strings into character arrays like we did in the version of the code which used sorting.

How do you usually check the frequency of any object ? If I were to give you a bag full of toys and asked you to tell me the type and the number of each type of toy, you would probably say – “There are 3 planes, 2 tennis balls and 1 football.” What did you just do ? We grouped each type of toy and starting counting them. You must be saying to yourself, “Why did he come up with an example of counting toys !”. Well, with a lockdown, with kids home and the ever increasing list of things to do, you better know everything about all the toys at home !

With strings, which are composed of characters, we need to count each type of character. You can imagine a string as a bag full of characters. In the toy example, we had only 3 items. It’s easy to remember 3 items and the count of each one of them. What if the bag had 15 items ? Would you be able to remember that along with the number of each type ? You would probably make a note of it and have 2 columns, toy type and count. In case of characters, we need to find out the type of character(letter) and the count of each character. So, we need 2 things, character type and count of each type. How many lower case letters can there be ? Well, 26. You wouldn’t make 26 variables now. How can we emulate a note like structure ? Well, an array can help us here. What should be the size of the array? 26, for 26 letters, ‘a’ – ‘z’.

        int[] frequencies = new int[26];

How do we maintain the count against each character ?

We have defined an array of size 26 to store the count of each character from ‘a to ‘z’. But how do we increase of count of ‘c’ if we get multiple ‘c’ ? Every letter has an Ascii code. For the letter ‘a’, it is 97, ‘b’ is 98 and so on. What if we could store the count of the character ‘a’ at index 0, ‘b’ at index 1 and so on? Well if the character in the string is an ‘a’ and we subtract an ‘a’ from it, we are actually saying ‘a’ –‘a’ or 97 – 97 which is 0. This can be used as an index into the frequency array which we defined above. If we get a ‘b’, we find the index of ‘b’ as ‘b’ – ‘a’ which is 98 – 97 = 1. So we access index 1 in the array. We do the same for every character we encounter in the string.

Now, we need to store the value at each index – the value will be the count of each character. The values in the array will be initialized to 0. Each time we encounter a character, we access the array at the correct index and simply increment the value.

Let’s take an example of 2 strings, “abby” and “baby”.

As shown above, the index of ‘a’ is 0, ‘b’ is 1 and so on. When we start visiting each character in the string “abby”, we perform a ‘character’ -‘a’ and simply increment the counter at that index. The value at index 1 is 2, this shows that ‘b’ occurs twice. The characters ‘a’ and ‘y’ appear only once. Using this logic, we have maintained the count of each character in the frequency array.

for (int i = 0; i < charactersOfFirst.length; i++) {
            frequencies[charactersOfFirst[i] - 'a']++;
}

What about frequency of the characters in the second string, “baby” ?

We could create another array and store the frequency of the characters in that 2nd array. Once we create that 2nd array, the 2nd array would have same values for the string “baby” since ‘b’ occurs twice and the characters ‘a’ and ‘y’ appear once. We could then iterate through arrays and compare the value at each index. If a value at an index is different, they are not anagrams.

Do we need a second array ? Can we use the same array for the 2nd string as well ? What we could do is simply decrement the count in the frequency array for each character that occurs in the 2nd string. So for the 2nd string, if we encounter an ‘a’, we go to the index of ‘a’, which is 0 and decrement the value at that index. This will make it 0 for the current example.

frequencies[charactersOfSecond[i] - 'a']--;

How does this help ? Well, if the frequency of the characters in the 2 strings are the same, the first increments it and the 2nd decrements it and at the end of it, all values in the array should be zero.

As shown in the figure above, when we iterate through the first string, we increment the count as shown in top half. In the bottom half, we decrement the values in the same array. The final values can be seen in the middle. In this case, since “abby” and “baby” have same frequency of characters, the entire array has value 0.

Combining all these changes in the code

public static boolean isAnagram(String first, String second) {

        char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();
        char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

        if (charactersOfFirst.length != charactersOfSecond.length) {
            return false;
        }

        int[] frequencies = new int[26];

        for (int i = 0; i < charactersOfFirst.length; i++) {
            frequencies[charactersOfFirst[i] - 'a']++;
            frequencies[charactersOfSecond[i] - 'a']--;
        }

        for (int frequency : frequencies) {
            if (frequency != 0) return false;
        }

        return true;
}

The 2nd for loop checks if any value in the frequency array is not equal to 0. A value other than 0 would indicate that either there is a different character or frequency of the characters do not match. A positive value would indicate a character in the first string that does not appear in the second and a negative one means the character appears in the 2nd string and not in the first.

Conclusion

Using a single array and the ascii code of the letter to count the frequency of the characters is a simple but effective approach to check if 2 strings are anagrams. In fact, this solution has a time complexity of O(n). We did reserve an array of size 26 but that is not much of a concern since we don’t resize the array. We could have avoided the use of the character array and used another string after removing the spaces and converting the string to lower case but I will leave that as an exercise for you. Happy anagramming !

In this blog I am going to give you a detailed understanding of how to find if two strings are anagrams of each other. We will first understand what an anagram is, consider different types of input data and then finally move on to write the code in Java. Like always, we will approach this step by step. Along the way, I will deliberately make a few mistakes which will result in incorrect results for a few cases. We will then fix the code so that we get the appropriate results for all inputs. This way, you will understand the code a lot better.

What is an anagram ?

An anagram is a word or a phrase formed by rearranging the letters of another word or phrase. This is straight out of wiki. I think it is a good read if you are interested in the history of anagrams and the application of anagrams.

Let us break the definition down into 2 parts –

1. ‘An anagram is a word or a phrase’ – The phrase part is important as most examples focus on just a single word.
2. ‘formed by rearranging the letters of another word or phrase’ – This is straightforward to understand – the key here is rearrangement.

Examples of Anagrams

1. “evil” = “vile” – Of course they don’t mean the same ! These are anagrams since the frequency of each character is the same in both words. It is just rearranging the characters in the word ‘evil’, which gives us the word vile.
2. “coronavirus” = “carnivorous” – same frequency of each character in the words coronavirus and carnivorous and just rearrangement of characters.
3. “debit card” = “bad credit”. This is a different kind of an example – a phrase ! Note that this has a space in between, make a note of this. The characters in the phrase on the left side have same frequency of characters as on the right side.
4. “William Shakespeare” = “I am a weakish speller”. A couple of different things to notice in this example – The name on the left side is in uppercase but the one on right side is in lowercase. Another observation is that the name has changed into a sentence. The frequency of the characters on the left side is still the same as on the right side, just rearrangement as usual.

Common observations

For 2 words or phrases to be anagrams –

1. The 2 words/phrases must have same characters along with same frequency.
2. They can have a space in between which we need to handle.
3. Upper/Lower case of the words/phrases should be handled appropriately.

Time for some code

We need to check if 2 strings/phrases are anagrams. Hence, the input will be 2 strings. Let’s assume that they are not null. If they are anagrams, we return a true else return false. This can easily be translated into a function in Java which takes 2 parameters and returns a boolean value. Let’s call that function, isAnagram.

public static boolean isAnagram(String first, String second) {

    return true;
       
}

The function, isAnagram, takes 2 parameters and returns true for the moment.

Let’s consider our first example of “evil” and “vile”. These are anagrams. The characters have been rearranged. What if we were to arrange them in the same way ?

To arrange the characters in the same way, we need the characters from the string. A string is made up of characters. We can use the toCharArray function on a string to get each character.

char[] charactersOfFirst = first.toCharArray();
char[] charactersOfSecond = second.toCharArray();

We have our character array from each string. How do we arrange them in the same way ? Well, we can sort the characters in each array using the Arrays class.

Arrays.sort(charactersOfFirst);
Arrays.sort(charactersOfSecond);

What is left now is simply checking if the sorted characters are the same. How do we do that ? We can use the Arrays. equals method for this and pass the sorted character arrays to it.

return Arrays.equals(charactersOfFirst, charactersOfSecond);

Combining the code from last 3 steps

public static boolean isAnagram(String first, String second) {

        char[] charactersOfFirst = first.toCharArray();
        char[] charactersOfSecond = second.toCharArray();

        Arrays.sort(charactersOfFirst);
        Arrays.sort(charactersOfSecond);

        return Arrays.equals(charactersOfFirst, charactersOfSecond);
}

Well, that’s it ! Passing the inputs as “evil” and “vile” gives us true. Passing inputs as “coronavirus” and “carnivorous” also give us true.

Pictorial view of code execution when input is “evil” and “vile”

Does this code work for all cases ?

If we were to pass the inputs as “customers”and “store scum”, the function returns false. It should have returned true. The characters are the same along with the frequency. However, did you notice that there is a space in the second word , store scum?

Do you remember that this was one of the scenario we were going to handle ? Well, now is the right time to handle it ! This is simple – just replace the space between the words with an empty string. How do we do that in Java? Use the replaceAll method from String class.The replaceAll method takes 2 parameters, a regular expression in String format and the replacement String. The regular expression for space is: “\s” and we need to replace it with “”, an empty string. So with this understanding, our modified code will be –

public static boolean isAnagram(String first, String second) {

    char[] charactersOfFirst = first.replaceAll("\\s", "").toCharArray();
    char[] charactersOfSecond = second.replaceAll("\\s", "").toCharArray();

    Arrays.sort(charactersOfFirst);
    Arrays.sort(charactersOfSecond);

    return Arrays.equals(charactersOfFirst, charactersOfSecond);
}

You can see the highlighted code for the changes. The extra ‘\’ in “\\s” is to escape the ‘\’ in the string “\s”. With this change, we get the correct output of true when the input is “customers” and “store scum”. If we were to pass the input as “debit card” and “bad credit”, we get true.

Are we done now ? Well, not really. If we were to pass the input as “William Shakespeare” and “I am a weakish speller”, we get false, which is the incorrect answer. The frequency of the characters is the same in both strings, we handled the space as well.

Why is it failing ? Did you notice that the characters ‘W’ and ‘S’ in the first input string are in capital letters but in the second string, they are in lower case. The character arrays are sorted based on the ascii codes for upper and lower case letters. Ascii code for upper case letters starting from ‘A’ begins from 65 and for ‘a’, it starts from 97. So sorting them with mixed case characters and then applying equals does not help. The Arrays.sort method sorts each character array in ascending format. So in each character array, you see upper case letters(lower ascii) first followed by lower case(higher ascii value). Let’s modify the code to handle this scenario.

public static boolean isAnagram(String first, String second) {

        char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();

        char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();
        
        Arrays.sort(charactersOfFirst);
        Arrays.sort(charactersOfSecond);

        return Arrays.equals(charactersOfFirst, charactersOfSecond);
}

As shown in the highlighted code above, we only add the call to the function toLowerCase(). We add this function call for both the inputs. By doing this, we treat characters in both inputs as lower case. Now, if were were to pass the input as “William Shakespeare” and “I am a weakish speller”, we get true, which is the correct input.

I know what you are thinking now. You must be saying , “Oh, please tell me that we are done now ! “. Well, just one more change and our code will be ready for all scenarios. In fact I would say the next change is more of an improvement.

Final changes to the code

We have handled spaces, case sensitivity and the contents of the string by converting it to a character array and then sorting it. But what if the input strings are of unequal length even after removing the spaces ? In this scenario, we don’t want to sort the array and compare them later. What we can do is simply check for the length of the 2 character arrays after we remove the spaces between the words.

public static boolean isAnagram(String first, String second) {

        char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();
        char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

        if (charactersOfFirst.length != charactersOfSecond.length) {
            return false;
        }

        Arrays.sort(charactersOfFirst);
        Arrays.sort(charactersOfSecond);

        return Arrays.equals(charactersOfFirst, charactersOfSecond);
    }

It would be incorrect to check for length of the input strings as the first step in the function. If the input strings were “William Shakespeare” and “I am a weakish speller” and we were to check for the length of the string before converting it into a character array, the code would return false. The length of the string “William Shakespeare” is 19 and length of “I am a weakish speller” is 22. Even though they are valid anagrams, comparing input string lengths would not be right.

Conclusion

We have handled most of the scenarios and I think the code above is the final version. But it is the final version using this approach of sorting the character array and using the Arrays.equals method to check for contents. This is not just a valid solution but a good solution as well. I have not considered a scenario where the string contains special characters but this can be handled in the same way we handled the spaces.

The code above which uses sorting has time complexity of O(n log n). We can improve this code further by using a different technique where we can avoid the sorting. I will definitely write another blog on this soon. Until then, Happy Anagramming !

In this blog we are going to find out all the permutations of a given string. Like always, we will first start from the basics – Understand what is a permutation of a string, break the procedure down into smaller steps and understand the procedure of finding out one permutation. Finally, we will write code in Java for the same. Along the way, I will also be explaining each line code and show you pictorial representations of the code execution so that you can visualize it better.

What is a permutation ?

Different ways of arranging a set of items is permutation. A string is a sequence of characters. Permutation of a string is arranging the characters of the string in different ways. Let’s take an example to understand this.

Permutation of a String

The string “ace” can be arranged as “ace”, “aec”, “cae”, “cea”, “eac”,”eca” – different arrangements of the characters a,c,e which make the string “ace”. Note that the string “ace” is of length 3 and we get 6 different permutations of the same – 3 factorial. If the input string was “aced”, we will get 24 permutations – 4 !

Observation about the permutations

Did you notice that the first 2 permutations “ace”, “aec” have a as the first letter and the 2 other letters are then concatenated to the letter a.

Extracting the first character ‘a’ from “ace” leaves us with the remaining characters “ce”. It can be rearranged as “ce” , “ec”. Finally appending each to “a” results in “ace” and “aec“.

If we single out the character ‘c’ in ace, we are left with “ae”. With “ae”, rearranging them gives us “ae” and “ea”. Appending this to ‘c’ results in “cae” and “cea“.

If we single out the character ‘e’ in ace, we are left with “ac”. With “ac”, rearranging them results in “ac” and “ca”. Appending this to ‘e’ results in “eac” and “eca“.

Translating these observations into a technical perspective

We are taking a single character from the given string, starting with ‘a’, moving on to ‘c’ and finally visiting ‘e’. This can be done using the charAt function. We also need a for loop as we need to single out each character from the string.

for(int i = 0; i < remainingString.length();i++) {
    char ch = remainingString.charAt(i);
    ...
}

For each character that we extract, we need the rest of the string. So when we extract ‘a’ from the “ace”, we need “ce” so that we can have different arrangements of “ce” to append it to ‘a’. When we extract ‘c’ from “ace”, we need “ae”. When we extract ‘e’ from “ace”, we need “ac”. In short, when we are at a particular iteration , i , in the for loop, we need a string from the characters before and after that character.

How do we extract the remaining characters ?

We make use of the substring function to do that. The variable ‘i’ in the for loop points to current single character that we extract. When we extract ‘c’ from “ace”, we need to get “ae”. We can get all characters before i by making a call to substring(0,i) and everything after i by calling substring(i+1). We append them to get the remaining string.

for(int i = 0; i < remainingString.length();i++) {
    char ch = remainingString.charAt(i);
    String next = remainingString.substring(0,i)  + 
                  remainingString.substring(i+1);
    ...
}

Applying recursion

What is clear so far is that we start with the first character and apply permutation with remaining characters. Then we choose the second character and apply permutation with remaining characters. We continue this way until we visit each character in the string. To do something like this, recursion can be a good choice.

So let us take the code above and add it to a function, permutations.

public void permutations(String remainingString , String permutation) {
    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        //Code here for recursive call to permutations
       }
}

This function takes 2 parameters – remainingString and permutation. Why do we need them ? Well, the parameter remainingString keeps track of length of string to produce one complete permutation of current string.The permutation parameter will keep track of the current permutation.The first time this code starts executing, the remainingString will be the input string, “ace”, and the permutation will be a blank string, “”, since we are yet to start finding permutations. Now we start with ‘a’,fix that and then extract “ce”. So ‘a’ will be stored in ch and “ce” will be stored in variable referred to as next.

What do we have so far ?

remainingString = “ace”, permutation = “”, ch = ‘a’, next = “ce”

What should the next step be?

The variable, permutation, so far is “”, it should be “a”. It is not a valid end permutation but an intermediate one. The current value is a “”. Appending “” to “a” gives us “a”. So let’s define a variable permute and assign it to permutation +ch.

            String permute = permutation+ch;

So the variable permute = “” + “a” = “a”

public void permutations(String remainingString , String permutation) {
    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String permute = permutation+ch;
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        //Code here for recursive call to permutations
       }
}

Now, remainingString = “ace”, permutation = “”, ch = ‘a’, next = “ce”, permute =”a”

The next logical step is working on “ce” to extract ‘c’. Once that is done, the intermediate permutation is “ac”. “a” from the previous iteration and ‘c’ extract from current one. When we extract ‘c’ from “ce”, what remains is “e”. This is the same sequence as previous steps.

The solution seems to repeat for the next sub-problem. This can be solved by recursion. We need to call the permutations function. It takes 2 parameters – remainingString and permutation. The variable, next, has value “ce” and permutation currently is “a”. Let’s make a call to permutations function and pass these parameters.

public void permutations(String remainingString , String permutation) {
    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String permute = permutation+ch;
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        //Code here for recursive call to permutations
        permutations(next,permute);
       }
}

After the first recursive call, remainingString = “ce”, permutation = “a”. When code above starts execution, i = 0 , ch = ‘c’ , permute = “a” + ‘c’ = “ac” , next = “e”. Note that when this call happens, i = 0 . This block will get executed twice as the for loop checks for length of remainingString. More on this later. Then there is a recursive call again to the function by passing “e”, “ac”.

In the next iteration, remainingString = “e”, permutation = “ac”. When the code starts executing, i = 0 , ch = ‘e’ , permute = “ace” , next = “”. Then there is a call to recursive function with “” and “ace”.

Now , remainingString = “” , permutation =”ace”. It looks like the remainingString is a blank string along with the fact that permutation is “ace”. We are in a recursive function, every recursive function should have some condition to return if it has processed it’s sub-problem. This part is now solved, isn’t it ? So we need a terminating condition – the length of the variable, remainingString, can be that condition. We simply check if it’s length is zero.

public void permutations(String remainingString , String permutation) {
    if(remainingString.length() == 0 ) {
        System.out.println(permutation);
        return ;
    }

    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String permute = permutation+ch;
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        permutations(next,permute);
       }
   }

After the execution of this code we get “ace” and this function returns. The code execution continues from the the location that it was called – this is really the previous step. Take a look at the following flows to get a better understanding. Start from the block which says start and then the steps have been numbered.Push and pop indicates recursive function calls and returning back from a function.

Snapshot of the function calls when i = 0 and input is “ace”

Step 1 will get executed twice as length of “ce” is 2. When i is 0, we get “ace” and when i =1 , we get “aec”. When the function returns from step 2, we go back to step 1 where i will become 1. This will cause step 4 to be executed.

Note that, all these steps are happening when input is “ace” and i = 0. When i =1, a similar set of steps will be executed producing 2 more permutations.

Snapshot of the function calls when i = 1 and input is “ace”

Snapshot of the functional calls when i = 2 and input is “ace”

The images below will give you a more detailed view of how the code and function calls execute. We call the function, permutations, pass the parameters “ace” and “”.

Snapshot of the code execution when input is “ace” and i=0

Snapshot of the code execution when input is “ace” and i=1

I have left out the code tracing when i=2, it can be a good exercise for you.

Conclusion

The number of lines of code that we had to write to produce the permutations is small but there is a lot that is happening behind the scenes.Such kind of problems are being asked in technical interviews. Irrespective of this, I think recursion is an important concept to understand and it is also a good fit for a good number of problems.

Recursion is not very straight forward to understand but I hope the pictorial representations and breaking up the code step by step have given you a good understanding of the same. I urge you to take a piece of paper and trace the execution for one particular iteration – this will not only solidify your understanding of the solution to the permutation problem but help you sharpen your skill set by understanding recursion.