Group Anagrams — Algorithmics

Group words that are anagrams of each other.

groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"})
// [[eat tea ate] [tan nat] [bat]]

The obvious way is quadratic

Compare every word against every group’s representative using valid anagram. That is $O(n^2 \cdot L)$ , and the comparison is doing the same work over and over.

Give each group a name

Two words are anagrams exactly when they have the same letter counts. So compute those counts once per word and use them as a key. Words with equal keys are anagrams, by definition, and a map does the grouping.

Word 1 / 6

eat → counts → aet

aet

eat

No bucket had this signature, so eat opens a new one. The signature is the letter counts — order thrown away deliberately.

func groupAnagrams(strs []string) [][]string {
    var groups = make(map[[26]int][]string)
    var result = make([][]string, 0)

    for _, str := range strs {
        var key = [26]int{}

        for _, char := range []byte(str) {
            key[char-'a']++
        }

        groups[key] = append(groups[key], str)
    }

    for _, val := range groups {
        result = append(result, val)
    }

    return result
}

$O(n \cdot L)$ — each word read once — against $O(n \cdot L \log L)$ for the sort-the-word version.

Arrays are comparable in Go; slices are not

map[[26]int][]string is the interesting line. Go permits an array as a map key because arrays are comparable — fixed length, compared element by element.

var key [26]int          // ✓ usable as a map key
var key []int            // ✗ invalid map key type []int

That distinction rules out the slice version entirely, and it is why the fixed 26 is not just an optimisation here — it is what makes the key possible at all.

In a language without comparable arrays you would serialise the counts to a string first ("1#0#0#…"), which is the same idea paying an allocation.

The other canonical key

Sorting each word produces a canonical form too:

r := []rune(str)
slices.Sort(r)
key := string(r)

$O(L \log L)$ per word instead of $O(L)$ , and no alphabet assumption. That last part matters: the count key needs a known, small alphabet, and breaks the moment uppercase, spaces or Unicode appear.

Use counts when the alphabet is fixed and small. Use sorting when it is not.

Iteration order

result is built by ranging over a map, and Go randomises map iteration order deliberately — it is not insertion order, and it differs between runs of the same binary.

That is fine here because the problem accepts any order. It would not be fine if the output were compared directly against a fixed expected value, which is a common way for tests around map-based code to become flaky.