Press "Enter" to skip to content

How to find out if two Strings are anagrams Java

Ajk 1

How to find out if two Strings are anagrams… When you first come across this problem you will probably think to yourself – easy, I know what an anagram is and I know how to find out if two Strings are anagrams… I can totally solve this problem! Just go through the first string and for every character check if it appears in the second one. Done. Now sure that would work… About the same way that flying north-east will eventually take you from Toronto to California… although it’ll take you a couple of days and you will probably have to go through North Korea at some point (Ouch!).

But is there a better way? Interviewers will most likely want you to prove you understand clearly if this can be improved and how. Well as a first step, let’s analyze the character by character checking method. I am not going to write code for that since it is pretty trivial (and it would look pretty horrible IMO :P), but instead let’s try to just lay down our algorithm for it and try to find what our bottlenecks are. Let’s see:

  • Time Complexity: For each letter in the first String (n) you will go through each letter in the other String (*n) making your time O(n2). (Double Ouch! On a second thought, maybe it’s better to travel through North Korea.. Ok, ok, I am just messing with you!)
  • Auxiliary Space Complexity: Just some temporary constant vars. O(1).

So on your venture to optimize the horrible algorithm from before, you will probably start thinking about optimizing the time complexity. Well we know that sorting takes only O(n*log(n)), (Check this out if you want to see more Sorting algorithm fun) so if we somehow applied it we could do much better. Let’s give it a try:

How to find out if two strings are anagrams – Java – Sorting

Let’s do a quick time/space complexity analysis. We have 3 operations done here sequentially:

  • Copying a String to a char array: Time – O(n) (time it takes to set each element of the array); Space – O(n) (Space the array takes)
  • Sorting an array: Time – O(n*log(n)) (you should know at least 1 algo which does this. If not, check MergeSort; Space – O(n) (we could optimize but we’ll leave it at that for now)
  • Comparing two arrays: Time – O(n) (going through the arrays at the same time); Space – O(1) (maybe a temporary counter might be needed).

So to sum this up we finish our analysis by stating the time complexity of our new algorithm will be O(n*log(n))

Homework Question #1: What is the space complexity of this algorithm?

Good, you might think. But the interviewer at this point will probably ask you if you can further optimize the algorithm you have. And you start thinking: What do we know about characters that we might be able to use to our advantage?
Chars are a finite set! In fact let’s take a look at the ascii extended table:

ASCII Table - Finding  If Strings Are Anagrams
ASCII Table – Finding If Strings Are Anagrams

We can use this to our leverage. We can create an array with all chars as indexes and count how many times it occurs in each String. Furthermore we can use only one array and increase the char count for the first String and decrease it for the second. The only case when the two Strings are anagrams is when the final array after increasing and decreasing will still have a count of 0. Meaning the amount of all specific chars in one array was equal to the amount of specific chars in the other. Anyway enough of this rant. Let’s try to put this in a clean step by step algorithm:

How to find out if two strings are anagrams – Algorithm

  1. Make an array of 256 ints, one per each possible char
  2. For each char in the first String, increase its int equivalent in the array by 1
  3. For each char in the second String, decrease its int equivalent in the array by 1
  4. If the array still has all 0s, then the Strings are anagrams!

Seems like we have it down in nice small trivial steps, so why not just get straight to coding!

How to find out if two strings are anagrams – Java – Cached Array

In this case we have the following analysis:

  • Time ComplexityO(n) (time to go through the arrays at once)
  • Space ComplexityO(1)

Homework Question #2: Why is the Auxiliary Space complexity O(1)? We are building an auxiliary array after all aren’t we?

Final thoughts: The above code makes one assumption – that we only have a finite set of 256 chars. (as is the case for ASCII extended set). Remember that assumptions are a huge pitfall in programming. So you should be very careful with them. State them clearly in your code.

I also put a small fun note to make the method about a billionth time faster :P, which is to use a decreasing for loop! (an increasing one would have resulted in more variables being created or length() accessed multiple times) This has no real-world use, so honestly… don’t try this at home :P. At this point, hopefully if you get asked this in an interview, you will easily build an implementation to find whether two strings are anagrams in Java.

Hope you guys enjoyed it… and I’ll see you guys next time ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂