Skip to main content

22. Group Anagrams

easyAsked at Tripadvisor

Cluster strings that are anagrams of each other — Tripadvisor applies this hash-map grouping pattern to deduplicate and cluster synonym hotel names or misspelled destination tags in their search index.

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 or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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 the characters of each string to produce a canonical key, then group all strings sharing that key using a hash map.

Time
O(n * k log k)
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. Frequency count as key (optimal)

Build a 26-length character-count array as the canonical key instead of sorting. Avoids the k log k sort cost per string.

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:

Tripadvisor-specific tips

Tripadvisor interviewers often frame this as a search-normalization problem — how do you canonicalize user-entered destination strings before indexing? The sorting approach is intuitive and fine to start with, but pivot to the frequency-count key when asked to optimize. Mentioning that this pattern underlies fuzzy deduplication of hotel names (e.g., 'The Ritz' vs misspelled variants) shows you understand the product context.

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

Practice these live with InterviewChamp.AI →