Skip to main content

49. Group Anagrams

mediumAsked at Anduril

Cluster a list of strings so that anagrams appear in the same group. Anduril uses this to test hash-map key design — choosing the canonical form of a key is the same challenge as selecting a canonical state representation when deduplicating path-planning states in a search algorithm.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-11)— Cited in Anduril SWE generalist onsite reports as a hashing and key-design exercise.
  • Blind (2025-09)— Anduril interview threads mention Group Anagrams as a medium hash-map problem in coding rounds.

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, 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"]]

Explanation: Anagrams share the same sorted-character key.

Example 2

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

Explanation: Empty string is its own group.

Example 3

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

Explanation: Single character, single group.

Approaches

1. Sort as key

Sort each string's characters to produce a canonical key. Group strings by their sorted key using a map.

Time
O(n * k log k) where k is 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 Array.from(map.values());
}

Tradeoff: Simple to implement. The k log k sort per string dominates. For most interview inputs this is fast enough and is the expected answer.

2. Character frequency as key

Encode each string as a 26-element frequency count and use that as the map key. Avoids sorting.

Time
O(n * k)
Space
O(n * k)
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const freq = new Array(26).fill(0);
    for (const ch of s) freq[ch.charCodeAt(0) - 97]++;
    const key = freq.join(',');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return Array.from(map.values());
}

Tradeoff: O(n * k) without the log k sort factor. Better for large k. The key is a string like '1,0,0,...,1,0,...' — joining with a separator avoids ambiguous concatenations (e.g. '10' vs '1,0').

Anduril-specific tips

Lead with the sorted-key approach and mention the frequency-key optimization. Anduril engineers appreciate when you explicitly discuss the key-design decision: 'I need a canonical form that maps all anagrams to the same value — sorted characters work, or a 26-element frequency vector for O(k) per string instead of O(k log k).' The separator in the frequency key is a subtle correctness point — mention it.

Common mistakes

  • Using the sorted key without a separator — '1,0,0' is unambiguous; '100' is not ('10,0' and '1,00' hash to the same string).
  • Initializing the group as undefined before pushing — check map.has(key) or use map.get(key) ?? [].
  • Returning Array.from(map.keys()) instead of map.values() — keys are the canonical forms, not the grouped strings.
  • Case sensitivity — problem says lowercase only, but if the input were mixed-case, you'd need to normalize first.

Follow-up questions

An interviewer at Anduril may pivot to one of these next:

  • What if the alphabet is arbitrary Unicode, not just 26 lowercase letters?
  • Group strings that are shifts of each other (all characters shifted by the same amount).
  • How would you extend this to group anagrams of arbitrary multi-word phrases?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why join frequency with a comma separator?

To avoid hash collisions: [1,11] and [11,1] have different frequencies but would map to the same string '111' without a separator.

Is sort().join() thread-safe in JS?

JS is single-threaded; no issue. In C++ or Rust you'd need to be more careful if building the key across threads.

Can an empty string be an anagram of another empty string?

Yes — both have all-zero frequency vectors, so they'd be in the same group.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →