Category: java

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.