Group Anagrams

Problem

Given a list of strings, group the ones that are anagrams, meaning they contain exactly the same letters in a different order. The groups can be returned in any order.

Approach

Give every word a key that is identical for all of its anagrams, then collect words by key in a dictionary.

A count of each letter from a to z works as that key. Turning the 26 counts into a tuple makes it hashable. Sorting each word also works, but counting avoids the extra log factor.

Solution

from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)

        for word in strs:
            counts = [0] * 26
            for char in word:
                counts[ord(char) - ord("a")] += 1
            groups[tuple(counts)].append(word)

        return list(groups.values())

Complexity

• Time: O(n · k), where n is the number of words and k is the longest word.
• Space: O(n · k) for the groups.

Edge cases

• Empty strings are anagrams of each other and land in one group.
• A single word returns one group with one word.
• The input is limited to lowercase English letters, which is what makes the 26-slot count valid.