49. Group Anagrams
mediumAsked at LinearGroup strings that are anagrams of each other. Linear uses this to see if you can design a canonical key for grouping — sorted string vs. character frequency array — and articulate the trade-off between the two.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Linear loops.
- Glassdoor (2026-Q1)— Reported in Linear SWE onsite reports as a hashing and string design problem.
- Blind (2025-12)— Cited in Linear interview threads as a recurring medium-difficulty question.
Problem
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
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"]]Example 2
strs = [""][[""]]Example 3
strs = ["a"][["a"]]Approaches
1. Sort each string as key
Sort the characters of each string; use the sorted string as a map key.
- Time
- O(n * k log k)
- Space
- O(n * k)
function groupAnagrams(strs) {
const map = new Map();
for (const str of strs) {
const key = str.split('').sort().join('');
if (!map.has(key)) map.set(key, []);
map.get(key).push(str);
}
return [...map.values()];
}Tradeoff: Clean and easy to reason about. O(k log k) per string due to sorting. For short strings this is fine — and it's the approach most interviewers accept at Linear.
2. Character frequency array as key (optimal for long strings)
Count each character's frequency into a 26-element array; serialize that as the key.
- Time
- O(n * k)
- Space
- O(n * k)
function groupAnagrams(strs) {
const map = new Map();
for (const str of strs) {
const count = new Array(26).fill(0);
for (const ch of str) count[ch.charCodeAt(0) - 97]++;
const key = count.join(',');
if (!map.has(key)) map.set(key, []);
map.get(key).push(str);
}
return [...map.values()];
}Tradeoff: O(k) per string instead of O(k log k) — better for very long strings. The key is a comma-joined count array like '1,0,0,...,1,0'. Slightly more code but asymptotically superior.
Linear-specific tips
Present both approaches to Linear interviewers and let them choose which to implement. The sort-based approach is simpler; the frequency-array approach is more efficient. Showing awareness of both signals algorithmic maturity. Always name your map key design pattern: 'I'm creating a canonical representation so all anagrams map to the same key.'
Common mistakes
- Using an unsorted string as the map key — anagrams won't match unless normalized.
- Joining the frequency array without a delimiter — '1''1''0' and '11''0' collide. Always use a separator like ','.
- Not handling the empty string — it groups with itself correctly, but only if the empty key is produced consistently.
Follow-up questions
An interviewer at Linear may pivot to one of these next:
- Valid Anagram (LC 242) — simpler version: just check if two strings are anagrams.
- Find All Anagrams in a String (LC 438) — sliding window to find anagram substrings.
- How would you group anagrams if the strings could contain Unicode characters?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does sort work as a canonical key?
Anagrams have identical characters in different orders. Sorting places them in the same order, making equal strings out of anagrams.
Why does the frequency array need a separator?
Without a separator, [1,12] and [11,2] produce the same joined string '112'. The comma distinguishes between separate counts.
Which approach should I code first?
Start with sort — it's two lines and immediately correct. Then offer the frequency variant as an optimization for long strings. Most Linear interviewers are satisfied with the sorted approach.