Group Anagrams

Try It Yourself

Use the editor below to group words that contain the same character counts. Preserve the order in which each group first appears and the input order inside each group.

Submit your implementation when it passes the examples. Remember that repeated characters and empty strings need stable signatures too.

Group Anagrams

mediumFrequency Counter · Hash Map · Strings30 minLC 49

Problem

Given an array of lowercase strings, group the strings that are anagrams of one another.

Return groups in the order their character signature first appears, and keep words inside each group in input order.

Example 1:

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

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

Example 2:

Input: words = ["a"]

Output: [["a"]]

Constraints

1 ≤ words.length ≤ 10,000
Every word contains lowercase English letters.

0 attempts

Solution

Build a 26-position frequency signature for each word. Anagrams produce the same signature even when their characters appear in a different order.

Use that signature as a map key. The first word creates a group, and later words with the same signature are appended to it.

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

  for (const word of words) {
    const counts = Array(26).fill(0);

    for (const character of word) {
      counts[character.charCodeAt(0) - 97]++;
    }

    const signature = counts.join("#");

    if (!groups.has(signature)) {
      groups.set(signature, []);
    }

    groups.get(signature).push(word);
  }

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

Big O notation

Measure	Complexity	Explanation
Time	`O(n · k)`	Every character of every word is counted once, where k is the average word length.
Auxiliary space	`O(n · k)`	The map and returned groups store the input words and their signatures.