49. Group Anagrams

Q: When does the frequency key outperform the sorted key?

For long strings (k >> 26). Sorting is O(k log k); frequency counting is O(k). At k = 100, the difference is modest. At k = 10,000, the frequency approach is meaningfully faster.

mediumAsked at Citadel

Group Anagrams is a hashing canonicalization problem: find a transformation that maps equivalent items to the same key. At Citadel, this pattern appears in symbol normalization (mapping ticker aliases to a canonical identifier) and in deduplication pipelines. The interview tests whether you choose the right canonical key — sorted string vs. frequency count.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2025-12)— Citadel SWE candidates list Group Anagrams as a common hash-map canonicalization question in technical coding rounds.
Blind (2025-09)— Citadel SWE threads note Group Anagrams tests hash-key design — an underrated skill Citadel probes explicitly.

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: Words with the same sorted characters form a group.

Example 2

Input

strs = [""]

Output

[[""]]

Explanation: Single empty string — one group.

Example 3

Input

strs = ["a"]

Output

[["a"]]

Explanation: Single character — one group.

Approaches

1. Sorted-string key

Sort each string's characters to form a canonical key. Use a Map from sorted string → list of original strings.

Time: O(n * k log k) where k is the max string length
Space: O(n * k)

function groupAnagrams(strs) {
  const map = new Map();
  for (const str of strs) {
    const key = str.split('').sort().join(''); // canonical key
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(str);
  }
  return Array.from(map.values());
}

Tradeoff: Simple and idiomatic. O(k log k) per string for the sort. For short strings (k ≤ 100) this is fast in practice. The expected answer for most interview settings.

2. Character-frequency key

Represent each string as a 26-element frequency array, serialized to a string key. Avoids sorting — O(k) per string.

Time: O(n * k)
Space: O(n * k)

function groupAnagrams(strs) {
  const map = new Map();
  for (const str of strs) {
    const freq = new Array(26).fill(0);
    for (const ch of str) freq[ch.charCodeAt(0) - 97]++;
    const key = freq.join(','); // e.g. '1,0,0,...,1,0,...'
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(str);
  }
  return Array.from(map.values());
}

Tradeoff: O(n*k) time — avoids the log k sorting cost per string. Better for very long strings. The key is 51 characters (26 counts + 25 commas) regardless of string content, so it's fixed-width and cache-friendly.

Citadel-specific tips

State both approaches and compare: 'Sorted key is O(k log k) per word; frequency array is O(k) per word. For k ≤ 100, both are fast, but the frequency approach is asymptotically better and more interesting to reason about.' Citadel interviewers appreciate knowing when to optimize and why. Also note the key-design pattern: 'Canonical key = any bijective transformation that maps equivalent items to the same hash — this generalizes far beyond anagrams.'

Common mistakes

Forgetting to initialize the map entry before pushing — calling push on undefined throws a TypeError.
Using the original string as the key instead of the sorted or frequency key — every word goes to its own group.
Joining the frequency array without a separator — '111' is ambiguous (is it [1,11] or [11,1] or [1,1,1]). Use a comma separator.
Not returning Array.from(map.values()) — Map values is an iterator, not an array.

Follow-up questions

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

Valid Anagram (LC 242) — check if two strings are anagrams using the same frequency approach.
Find All Anagrams in a String (LC 438) — sliding window frequency matching.
How would you group strings that are rotations of each other (not just anagrams)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

When does the frequency key outperform the sorted key?

For long strings (k >> 26). Sorting is O(k log k); frequency counting is O(k). At k = 100, the difference is modest. At k = 10,000, the frequency approach is meaningfully faster.

Why is the frequency key valid as a Map key?

JavaScript Map uses SameValueZero for object comparison, but string keys are compared by value. The frequency array serialized to a string is a deterministic representation — equal frequency arrays produce equal key strings.

Can you use a hash function instead of sorting?

Yes — multiply prime numbers by character frequencies (polynomial rolling hash). But collisions are possible. For correctness, sorting or exact frequency keys are preferred in interviews.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →