DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Group Anagrams

mediumArrays and hashing Must-do

Problem statement

You are given a list of lowercase words strs. Group together the words that are anagrams of each other, meaning they use the same letters the same number of times. Return the list of groups. The groups, and the words inside each group, can be in any order.

Examples

Example 1

Input: strs = ["tar", "rat", "cat", "art", "act", "dog"]

Output: [["tar", "rat", "art"], ["cat", "act"], ["dog"]]

Explanation: tar, rat and art all sort to art. cat and act sort to act.

Example 2

Input: strs = ["", "b", ""]

Output: [["", ""], ["b"]]

Explanation: The two empty strings are anagrams of each other.

Hints

Approach

Give every word a key that all its anagrams share: its letters in sorted order. Then one dictionary from key to list of words does the grouping in a single pass.

  1. Create a dictionary whose values are lists.
  2. For each word, compute key = sorted letters of the word.
  3. Append the word to groups[key].
  4. Return all the dictionary's values.

The only per-word cost left is sorting its letters, which is O(k log k).

ComplexityTime O(n · k log k)Space O(n · k)
Python
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for word in strs:
groups["".join(sorted(word))].append(word)
return list(groups.values())

Follow-up questions

  • Return only the largest group.
  • Group log messages that differ only in the numbers they contain.

Frequently asked questions

Yes. Count the 26 letters and use the tuple of counts as the key (in Java, join the counts into a string such as "1#0#2#..."). That makes each key O(k) instead of O(k log k), so the total is O(n · k). For short words the sorted key is usually just as fast in practice.

Lists are mutable, so they are not hashable. Convert the sorted letters to a string with "".join(...) or to a tuple before using them as a key.

It is the general "normalise, then group by key" pattern. Grouping log lines by a normalised message (numbers and IDs stripped out) to find the most common error types works the same way.