Skip to main content

24. Group Anagrams

mediumAsked at Expedia

Cluster strings that are anagrams of each other — Expedia applies the same canonical-key grouping to cluster airport code aliases and alternate-spelling city names into a single inventory bucket.

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

Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word formed by rearranging the letters of another.

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
[["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2

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

Approaches

1. Sort each string as key

Sort each string's characters to produce a canonical key. Strings with the same sorted form are anagrams; group them in a hash map.

Time
O(n * k log k) where k = max string length
Space
O(n * k)
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:

2. Character-count key (no sort)

Build a 26-element frequency array per string and stringify it as the map key. Avoids the sort, reducing per-string work from O(k log k) to O(k).

Time
O(n * k)
Space
O(n * k)
function groupAnagrams(strs) {
  const map = new Map();

  for (const s of strs) {
    const count = new Array(26).fill(0);
    for (const c of s) count[c.charCodeAt(0) - 97]++;
    const key = count.join(',');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }

  return [...map.values()];
}

Tradeoff:

Expedia-specific tips

Expedia interviewers appreciate when you call out the practical trade-off: the sort key is simpler to maintain; the frequency-count key wins at scale. If the interviewer pushes on Unicode airport codes or non-ASCII city names, note that the frequency-count approach needs a wider character table — a sign they want production thinking.

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 Expedia interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →