LESSON 247 OF 348 · HASH TABLE

Group Anagrams in Kotlin: O(n · L log L) with Sorted Keys

Practice O(n * L * log L) Read the full explanation

Given an array of strings, group the anagrams together. You can return the answer in any order.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Example:

Input:   strings = ["eat","tea","tan","ate","nat","bat"]

Output:  [["bat"],["nat","tan"],["ate","eat","tea"]]

Note:

Your algorithm should run in O(n * L * log L) time and use O(n * L) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Group Anagrams in Kotlin, explained

Problem overview

The function groupAnagrams receives an Array<String> called strings and returns a List<List<String>>: the words split into groups, where all the words in one group are anagrams of each other. Two words are anagrams when one is a rearrangement of the other's letters, using every letter exactly once. The groups, and the words inside them, can come in any order.

For ["eat", "tea", "tan", "ate", "nat", "bat"] the groups are eat, tea, ate, then tan, nat, then bat alone. Every word lands in exactly one group, and a word with no anagram partner gets a group of its own.

With n words of length at most L, the statement asks for O(n * L * log L) time and O(n * L) extra space.

Approach: anagrams share a sorted form

Comparing every pair of words would take O(n²) comparisons. The better idea is to give each word a key that is identical for all of its anagrams and different for everything else. Sorting the letters of a word does exactly that: eat, tea and ate all become aet, while tan and nat become ant, and bat becomes abt.

Then a HashMap from the sorted key to a list of the words that produced it does the grouping. For each word, compute its key, find or create the list for that key, and add the word. When all the words are processed, every list in the map is one complete group, so the map's values are the answer.

Sorting one word of length L costs O(L log L), and it is done once per word, which gives the O(n * L * log L) total. The map operations cost about O(L) each, since hashing and comparing a key reads its characters, and that is smaller than the sorting cost. The keys and lists together hold about n * L characters, hence O(n * L) space.

Step by step

Create the map. groupBySorted is a val holding an empty HashMap<String, MutableList<String>>. The list type is MutableList because each group grows as words arrive.
Loop over the words. for (s in strings) routes each word to its group.
Compute the key. sortedString comes from s.toCharArray(), sorted with sortedArray() and wrapped in String(...). Strings are immutable in Kotlin, so the sorting happens on a CharArray and the result is turned back into a string.
Create the group on first sight. If the map doesn't contain sortedString, store an empty mutable list under that key.
Add the word. Read the list with groupBySorted[sortedString] and call add(s). The map returns a nullable type, so !! asserts that the list exists. The previous step guarantees it.
Return the groups. Wrap the map's values in an ArrayList, which gives the List the function must return.

The solution in Kotlin

class Solution {
    fun groupAnagrams(strings: Array<String>): List<List<String>> {
        val groupBySorted = HashMap<String, MutableList<String>>()
        for (s in strings) {
            val sortedString = String(s.toCharArray().sortedArray())
            if (!groupBySorted.containsKey(sortedString)) {
                groupBySorted[sortedString] = mutableListOf()
            }
            groupBySorted[sortedString]!!.add(s)
        }
        return ArrayList(groupBySorted.values)
    }
}

Kotlin details worth knowing:

sortedArray() returns a new sorted CharArray and leaves the original alone. The similar-looking sorted() returns a List<Char>, which String(...) would not accept.
String(chars) builds a string from a CharArray. Two strings with the same characters are equal under == and have the same hash, which is what makes them work as map keys.
groupBySorted[sortedString] has the type MutableList<String>?. The !! operator turns a null into an exception, so use it only when, as here, you know the key is present.
mutableListOf() needs no type argument in groupBySorted[sortedString] = mutableListOf(), because Kotlin infers it from the map's value type.
groupBySorted.values is a view of the map. ArrayList(...) copies it into a standalone list. An ArrayList<MutableList<String>> is accepted as a List<List<String>>, because Kotlin's read-only List is covariant.

Complexity

Time is O(n * L * log L): one sort of at most L characters per word, plus map work that is about O(L) per word. Space is O(n * L): every word is stored once in a group and once as part of a key, in the worst case where no two words are anagrams.

Edge cases and common mistakes

Empty array. The map stays empty and the function returns an empty list.
The empty string. Its sorted form is also the empty string, a valid key, so empty strings form one group together.
No anagrams. Each word gets a one-element group.
Duplicate words. "eat" twice goes into the same group twice, since lists allow repeats.
Case. Sorting treats 'A' and 'a' as different characters, so "Eat" and "tea" are not grouped. The lesson compares letters as they are.
Passing sorted() to String(...). sorted() returns a List<Char>, and the compiler reports that none of the String constructors is applicable. Use sortedArray() to keep a CharArray.
Using the word itself as the key. Then no two different words ever share a group.
Forgetting to create the list first. Calling !!.add on a missing key throws a NullPointerException.

Testing

["eat", "tea", "tan", "ate", "nat", "bat"] gives three groups: eat, tea, ate; tan, nat; and bat.
[] gives an empty list.
["a"] gives one group holding a.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free