Group Anagrams

The problem

Given a list of lowercase words strs, put the words that are anagrams of each other into the same group and return the list of groups. Two words are anagrams when one is a rearrangement of the other's letters. Every word goes into exactly one group: a word with no anagram in the list forms a group by itself, and a word that appears several times is listed that many times. The groups, and the words inside a group, may be in any order.

What to write

function solve(strs: string[]): string[][]

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

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

Input
strs = [""]

Output
[[""]]

Constraints

Words contain lowercase English letters; 1 ≤ strs.length ≤ 10000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 words. Comparing every word with every other word to test for anagrams is far too many checks, so find something you can compute for one word alone.

2. Hint 2: Ask a smaller question

   Take "eat", "tea" and "ate". What could you compute from each word, separately, that comes out identical for all three and different for "tan"?

3. Hint 3: Name the pattern

   Give each word a key that its anagrams share, such as its letters in sorted order, and keep a hash map from key to the list of words with that key. Finding a word's group is then a hash map lookup. Read the lesson on hash map lookup.

4. Hint 4: State the invariant

   Two words get the same key exactly when they are anagrams. So after any number of words, each list in the map holds all the words seen so far that are anagrams of one another.

5. Hint 5: Sketch the pseudocode

   Start with an empty map. For each word: sort its letters to make the key; if the key is new, give it an empty list; add the word to the key's list. Return all the lists.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Use a sorted copy of each word as a key and collect the original words under that key.

The slow way

For each word, look through the groups made so far and test it against one member of each with an anagram check. It is correct, but a list where no two words match makes every word test against every earlier one.

The insight

Sorting a word's letters gives the same result for every anagram of it and a different result for anything else. That result can serve as a label, and a hash map finds the group with a given label in one step.

Step by step

1. Collect the words under a key that all their anagrams share. A hash map from key to list finds the right group in one step, however many groups there are.
2. The key is the word's letters in sorted order. Sorting ignores the order of the letters and keeps their counts, which is exactly what anagrams have in common.
3. Start a group the first time a key appears. The first word with a new key has no list to join yet, so an empty one is made for it.
4. Put the word in its key's group. The original word is stored, not its sorted key, because the answer must contain the words as they were given.
5. The groups are the answer; the keys are no longer needed. Each list in the map is one complete group of anagrams. The keys only served to find them.

The same numbered steps are the comments in each solution.

function solve(strs) {
  // 1. Collect the words under a key that all their anagrams share
  const groups = new Map();
  for (const word of strs) {
    // 2. The key is the word's letters in sorted order
    const key = [...word].sort().join("");
    // 3. Start a group the first time a key appears
    if (!groups.has(key)) groups.set(key, []);
    // 4. Put the word in its key's group
    groups.get(key).push(word);
  }
  // 5. The groups are the answer; the keys are no longer needed
  return [...groups.values()];
}

function solve(strs: string[]): string[][] {
  // 1. Collect the words under a key that all their anagrams share
  const groups = new Map<string, string[]>();
  for (const word of strs) {
    // 2. The key is the word's letters in sorted order
    const key = [...word].sort().join("");
    // 3. Start a group the first time a key appears
    if (!groups.has(key)) groups.set(key, []);
    // 4. Put the word in its key's group
    groups.get(key)!.push(word);
  }
  // 5. The groups are the answer; the keys are no longer needed
  return [...groups.values()];
}

def solve(strs):
    # 1. Collect the words under a key that all their anagrams share
    groups = {}
    for word in strs:
        # 2. The key is the word's letters in sorted order
        key = "".join(sorted(word))
        # 3. Start a group the first time a key appears
        if key not in groups:
            groups[key] = []
        # 4. Put the word in its key's group
        groups[key].append(word)
    # 5. The groups are the answer; the keys are no longer needed
    return list(groups.values())

Example 1, traced

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

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

Why it works

Two words have the same sorted letters exactly when they are anagrams. So words that belong together always land in the same list, and words that do not never share one. Every word is added to exactly one list.

Time and space

Time O(n k log k), extra space O(n k). Sorting a word of k letters takes about k log k steps, and it is done once for each of the n words: O(n k log k) time. The map stores every word and a key for each group, so the space is O(n k).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Store the original word in the group, not the sorted key. A group of keys would be the same string repeated.
• Turn the sorted letters back into a string before using them as a key. A list does not work: JavaScript treats two lists with the same letters as different keys, and Python refuses a list as a key.

Pattern

Hash map lookup. Builds on Valid Anagram and Two Sum.

Keep going