Skip to main content

17. Group Anagrams

mediumAsked at Squarespace

Cluster strings that share the same letters; Squarespace uses it to test whether you choose a canonical-key strategy over pairwise comparisons.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of lowercase strings, group together the anagrams. Return the groups in any order.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Pairwise anagram check

Compare every string to every group's first entry by sorting.

Time
O(n^2 * k log k)
Space
O(nk)
const groups=[];
for(const s of strs){
  const sorted=s.split('').sort().join('');
  const g=groups.find(g=>g.key===sorted);
  if(g) g.items.push(s); else groups.push({key:sorted,items:[s]});
}
return groups.map(g=>g.items);

Tradeoff:

2. Hash by sorted key

Use the sorted string as a canonical hash-map key so each lookup is O(1) average.

Time
O(n * k log k)
Space
O(nk)
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

Tradeoff:

Squarespace-specific tips

Squarespace likes when you mention using a 26-length count array as the key for shorter strings, and how the same canonical-key trick groups duplicate media assets at upload.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Group Anagrams and other Squarespace interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →