Skip to main content

49. Group Anagrams

mediumAsked at Linear

Group 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 Alex Chen, 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^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
[[""]]

Example 3

Input
strs = ["a"]
Output
[["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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →