Group Anagrams

You are given a list of lowercase strings strs. Two strings are anagrams of each other if one can be turned into the other by reordering its letters, i.e. they contain exactly the same letters with the same counts.

Split the strings into groups so that every string is in exactly one group and two strings share a group exactly when they are anagrams. Return the list of groups.

The groups may be listed in any order, and so may the strings inside each group. If a string occurs several times in the input, every copy appears in its group.

Example 1

Example 2

Example 3

Constraints

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] contains only lowercase English letters

Pattern Path · Hashing & Counting · problem 8 of 169

Start simple

Compare each string with a representative of every existing group (sorting or counting letters each time): O(n² · k) time for n strings of length up to k.

The key idea

The key observation is that being anagrams is an equivalence: if you can compute a canonical form that is the same for all anagrams and different for non-anagrams, grouping becomes a single dictionary pass.

Two canonical forms work well:

• Sorted letters. Sorting a word's characters gives one fixed spelling for its whole anagram class. Cost: O(k log k) per word.
• Letter counts. A tuple of 26 counts describes exactly which letters, and how many of each, a word uses. Cost: O(k) per word, plus a fixed 26 to build the key.

Create a dictionary from key to list. For each string, compute its key and append the string to that key's list. Strings land in the same list precisely when their keys are equal, which happens precisely when they are anagrams. The dictionary's values are the answer.

The sorted-letters key is shorter to write and fast for short words; the count key is asymptotically better for long words. Either one avoids comparing strings against each other, which is what turns a quadratic algorithm into a linear one.

Complexity

• Time: O(n · k log k) (or O(n · k) with count keys)
• Space: O(n · k)

Python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for word in strs:
            key = "".join(sorted(word))  # same for every anagram of word
            groups[key].append(word)
        return list(groups.values())

JavaScript

var groupAnagrams = function(strs) {
  const groups = new Map();
  for (const word of strs) {
    const key = [...word].sort().join(''); // same for every anagram of word
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
};

What the interviewer is checking

The interviewer wants to see you design a hash key that captures an equivalence relation, and discuss the trade-off between sorted-string keys and count-vector keys.

Mistakes to avoid

• Using a mutable list (or an unhashable array) as a dictionary key; convert counts to a tuple or a string.
• Building a count key like "1" + "11" without separators, which can make different counts collide.
• Dropping duplicate strings or the empty string.

Follow-ups to expect

• What if the strings use full Unicode? (Sorted key, or count map as key.)
• How would you do this across machines? (Map-reduce on the canonical key.)
• Return only groups of size two or more? (Filter the dictionary values.)

In real software

Bucketing records by a canonical key is how deduplication, spell-checker suggestion tables and search indexes group equivalent items, such as normalised email addresses or product names.

Practice next