Beating AlgoExpert: Group Anagrams

Back with another article on beating AlgoExpert. Today’s challenge is grouping anagrams together. The problem is available on AlgoExpert here as well as on Leetcode here.

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, for example, “Stop, hire Mark now!” could be rearranged to “I know he smart pro!” (Just a subtle hint to any recruiters that happen to be reading my stories.)

In full disclosure, the solution I created was done before I looked at the Leetcode solution which actually mimics mine. In fact, in looking at the solutions posted on Leetcode, I discovered an even more clever way using multiplication of primes which I am rather jealous I did not think of myself. I will cover that at the end.

The Prompt!

Quite simply, given an array of words, group each anagram together and return the group of anagrams. It should be noted that we are only using lowercase a-z characters in this prompt.

AlgoExpert’s Word Sort Method

An easy approach would be to sort every word alphabetically and use that sorted word as a key to group the words. For example if you took the words: “act,” “tac,” and “cat.” and sorted each one, you would find that they would all come out to “act” and thus they would all go into the same array. Using this method, you can build a solution like so:

Adding in the word.split().sort().join() method on line 7 increase their time complexity to O(w * n * log (n)), where w is the number of words and n is the length of the longest word. Now imagine that the words weren’t small words such as “yo” and “foo,” what if they were long phrases or made up words that are 100s of characters long? That n * log(n) time complexity to sort each word can get a little expensive. Here’s how you escape it.

Thinking in Finite Realms

As I pointed out, we are only concerned with letters of the alphabet, and there are only 26 of them. This is a huge advantage to use, since we are aren’t often dealing with small finite options as an input. Therefore we can go through in one pass of the word and count the number of times each letter occurs. We can store these counts in an Array of size 26, where the index of the array correlates with the position of the letter in the alphabet. For example, if we looked at “act,” “cat,” and “tac,” we would end up with something like this:

Order doesn’t matter, so any word that has exactly one of each letter: “a,” “c,” and “t,” would all be part of the same anagram.

We can then join this array using any sort of non-numeric delimiter such as a comma or period and get a string to use as the key for object storage. No matter how long the word is whether it is one letter or 1,000 letters, the array will always be of size 26 so joining it will be of constant time.

Putting the rest together should be a breeze after that, here is my solution:

By using this method, we drop the log (n) time complextity and achieve a big O run time of (w * n) where w is the number of words and n is the average length of each word.

Leetcode’s Prime Solution

As I mentioned above, at Leetcode I discovered a solution that uses the multiplication of prime numbers. Each letter of the alphabet is designated with a distinct prime number. Starting with a base of 1, as we go through each letter of a word, we multiply by the prime number associated with that letter. Since we are using prime numbers, there is no way two different anagrams could have the same product, and thus we can use the final product as the key. I provided the example below:

This solution still utilizes a runtime of O (w * n) so we are not actually getting a more efficient solution in terms of Big O run time, but it does drop some steps and should run slightly faster.

Remember this…

The big takeaway from this problem is to recognize when you have a finite area to work within. It can seem unusual to write an object or array of length 26, but doing so greatly increased our speed and knowing when you have a finite workspace can create great efficiencies.

Hope you enjoyed the read. Please like and share if you enjoyed and I really do appreciate any comments whether good or bad. Thanks for reading!