Group Anagrams

The problem

Group strings that are anagrams of each other. Order of groups and within groups can be anything.

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

Brute

For each string, compare to every group leader with sorted equality. O(n² · L log L).

Approach A — sort as key

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = [...s].sort().join("");
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(s);
  }
  return [...map.values()];
}

Time	O(n · L log L)
Space	O(n · L)

Approach B — count signature (often faster)

26 lowercase letters → key like 1#0#2#... or String.fromCharCode packing.

function groupAnagramsCount(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const cnt = new Array<number>(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    const key = cnt.join("#");
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(s);
  }
  return [...map.values()];
}

Time	O(n · L)
Space	O(n · L)

Why not XOR / sum of codes?

Collisions. "ac" and "bb" can collide on weak hashes. Sorted string or full counts are safe.

Edge cases

• Empty string "" — its own group key
• Single letters
• All identical
• Unicode — problem usually a–z; say so

Common mistakes

• Sorting the input array in place as “grouping” without a map
• Using object keys without care for key collisions
• Comparing lengths only

Interview delivery

1. Anagram ⇒ same multiset of chars.
2. Map signature → list.
3. Sort vs count keys.
4. O(nL) count version.
5. Empty string case.

Mental model

Anagrams share a character multiset. Any injective fingerprint of that multiset works as a hash key. Sorting characters is simple; counting is linear in string length.

Production cousin: grouping fuzzy search keys, deduplicating menu labels, or clustering tokens in NLP pipelines.

Complexity table

Keying strategy	Time per string	Collision-safe?
sorted chars	O(L log L)	yes
count[26] join	O(L)	yes (for a–z)
prime product	O(L)	overflow / collision risk
sum of codes	O(L)	no

Worked counts

"eat" → a1 e1 t1
"tea" → same key → same bucket
"tan" → a1 n1 t1 → other bucket

Out-loud answer

“Map fingerprint → list. I’ll count 26 letters and join counts as the key for O(nL). Sorted string keys are fine too. Return map values. Empty string is just another key.”

Interview delivery

1. Same multiset → same group.
2. Count signature key.
3. Map to lists.
4. O(nL).
5. Empty string group.

Tiny test plan

[""] → [[""]]; ["a"] → [["a"]]; classic eat/tea/tan sample has three groups.

Related

• Valid Anagram
• Two Sum
• Contains Duplicate
• Longest Consecutive Sequence
• JavaScript Interview Guide

Further reading

• LeetCode 49 — Group Anagrams
• MDN: Map