Marauder Bot

Problem

You are given a list of strings. Group the strings so that every string in a group is an anagram of every other string in that group, and return the groups; the order of the groups and the order of strings within each group do not matter.

Example. For ["eat", "tea", "tan", "ate", "nat", "bat"], the result is three groups: ["eat", "tea", "ate"], ["tan", "nat"], and ["bat"].

Key idea

Comparing every pair of strings for an anagram match works but scales quadratically with the list size. A better move is to give every string a canonical form that is identical for all of its anagrams but different for anything else, then group by that form.

Two canonical forms work well: the sorted characters of the string, since anagrams sort to the exact same sequence, or a fixed-length vector of letter counts, since anagrams share identical counts. Compute this key for each string, use it as a hash map key, and append the original string to the list stored under that key. One pass over the input leaves the map's values as exactly the desired groups. Sorting each string costs O(k log k) for length k, while counting costs O(k) but produces a bulkier key.

Solution

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();

  for (const str of strs) {
    const key = str.split('').sort().join(''); // anagrams share this sorted form
    const group = groups.get(key);
    if (group) {
      group.push(str); // add to the existing bucket for this key
    } else {
      groups.set(key, [str]); // first string seen with this key
    }
  }

  return Array.from(groups.values());
}

Complexity

Time: O(n · k log k) using sorted-string keys, where n is the number of strings and k the average string length, or O(n · k) using character-count keys.
Space: O(n · k). The map stores every input string along with its key.

Watch out for

Choose a key that cannot collide for non-anagrams; a key based only on which letters are present, ignoring counts, would wrongly merge strings like "aab" and "ab".
Words that appear alone still form a valid group of one; do not drop singleton groups.
Empty strings are anagrams of each other and form their own group if present.

Pattern

This is canonicalization plus hash-map bucketing: reduce each item to a normalized signature, then group items sharing a signature. The same "normalize, then bucket" instinct applies to any problem asking you to group items that are equivalent under some transformation.

Group Anagrams