49. Group Anagrams
mediumAsked at CitadelGroup 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 Sam K., Founder, InterviewChamp.AI · Last verified
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^40 <= strs[i].length <= 100strs[i] consists of lowercase English letters.
Examples
Example 1
strs = ["eat","tea","tan","ate","nat","bat"][["bat"],["nat","tan"],["ate","eat","tea"]]Explanation: Words with the same sorted characters form a group.
Example 2
strs = [""][[""]]Explanation: Single empty string — one group.
Example 3
strs = ["a"][["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.
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.