[Java] Group anagrams

Given a list of strings, group all anagrams together.

Example:

asd, lol, dsa

return:

[lol], [asd,dsa]

Anagrams are words of the exact same length with the exact same characters, potentially in different places.

We can use this to our advantage to easily determine whether two strings are anagrams of each other using an idea similar to a basic string compression algorithm. We create a fixed size array with a slot for each character in the alphabet (26 total, 0 = 'a' and 25 = 'z') and we process each string counting how many times each character appears in it.

We then create a string from that array using a fixed format: Xchar1...YcharN

We can now use this string as key for a map, which will quickly determine whether two strings are anagrams of not. All strings that are anagrams are added as values to the same map bucket, we then simply collect all values in an output list.

This uses O(N) time as we process all strings once and do constant work for each (alphabet size is fixed at 26) and O(N) space as we store all strings in our map.

You can check my implementation of groupAnagrams on my Gist along with some tests in GroupAnagramsJTests.