Group Anagrams

Difficulty: Medium

You're given a list of strings. Group together every string that's an anagram of another - meaning they contain exactly the same letters, just in a different order.

Return the groups as a list of lists. Each input string must end up in exactly one group, but the groups themselves can come back in any order, and the strings within a group can be in any order too.

Examples

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

"eat", "tea", and "ate" all use the same three letters. "tan" and "nat" share another set of letters. "bat" doesn't match anything else, so it sits alone in its own group.

Input: strs = [""]
Output: [[""]]

A single empty string just forms its own group.

Input: strs = ["a"]
Output: [["a"]]

Constraints

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Approach

A direct way to solve this is to go through the strings one at a time, and for each one, check it against every group formed so far to see if it belongs there (using the same kind of anagram check you'd use for two strings). That works, but comparing each new string against every existing group adds up as the list grows.

A cleaner approach relies on the fact that anagrams, once their letters are sorted alphabetically, turn into the exact same string. That sorted string acts as a signature - every anagram of a word shares the same signature. Using a hash map from signature to the list of original strings that share it, the whole list can be grouped in a single pass.

Solutions

Brute Force - Compare Against Existing Groups

For each string, check it against the first string of every group formed so far. If it's an anagram of that group's representative, add it there; otherwise, start a new group. Checking whether two strings are anagrams is done with a simple letter-count comparison.

function groupAnagrams(strs) {
  const groups = [];

  for (const str of strs) {
    let placed = false;

    for (const group of groups) {
      if (isAnagramOf(str, group[0])) {
        group.push(str);
        placed = true;
        break;
      }
    }

    if (!placed) {
      groups.push([str]);
    }
  }

  return groups;
}

function isAnagramOf(a, b) {
  if (a.length !== b.length) return false;

  const counts = {};
  for (const ch of a) counts[ch] = (counts[ch] || 0) + 1;

  for (const ch of b) {
    if (!counts[ch]) return false;
    counts[ch]--;
  }

  return true;
}

Time: O(n² · k), where n is the number of strings and k is their max length · Space: O(n · k)

Optimal - Sorted String as Hash Key

For every string, sort its letters alphabetically to build a signature key - anagrams always produce the same key. Use a hash map from that key to the list of original strings sharing it, then return all the map's values as the groups.

function groupAnagrams(strs) {
  const groups = new Map();

  for (const str of strs) {
    const key = str.split("").sort().join("");

    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key).push(str);
  }

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

Time: O(n · k log k), where n is the number of strings and k is their max length · Space: O(n · k)