Skip to main content

49. Group Anagrams

mediumAsked at AMD

Group strings that are anagrams of each other. AMD tests this to check hash-key design — generating a canonical key from unsorted data is analogous to instruction fingerprinting and opcode normalization in compiler IR passes.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Group Anagrams appearing in medium coding rounds as a hash-map design problem.
  • Blind (2025-11)— AMD interview threads list Group Anagrams as a core medium that tests canonical-key reasoning.

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 another.

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: Strings with the same sorted characters form groups.

Example 2

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

Explanation: Empty string is its own group.

Approaches

1. Sort each string as key

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

Time
O(n * k log k)
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 [...map.values()];
}

Tradeoff: O(n * k log k) where k is max string length. Simple and readable. The sort is the bottleneck.

2. Character frequency as key

Instead of sorting, build a 26-element frequency array and use it as the key. Avoids O(k log k) 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 [...map.values()];
}

Tradeoff: O(n * k) — linear in total characters. The '#' separator ensures keys like [1,11] and [11,1] don't collide. This is the asymptotically optimal approach.

AMD-specific tips

AMD compiler teams build canonical hash keys for IR instructions constantly — normalizing operand order, instruction patterns, or register allocations before hashing into a table. Frame the frequency-vector key as 'a canonical fingerprint': any two anagrams produce the same frequency vector, and the '#' separator prevents collisions between different-length slot values. Mention collision safety explicitly — AMD engineers care about correctness in hash-based lookups.

Common mistakes

  • Using freq.toString() as the key without a separator — '1,11' and '11,1' may serialize identically depending on implementation.
  • Sorting the original string and modifying strs — always sort a copy.
  • Returning an array of maps instead of arrays of strings.
  • Assuming all characters are lowercase ASCII without confirming the constraint.

Follow-up questions

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

  • Valid Anagram (LC 242) — check if two strings are anagrams (simpler single-comparison version).
  • Find All Anagrams in a String (LC 438) — sliding window variant.
  • How would you generalize 'canonical key' grouping to instruction scheduling in a GPU shader compiler?

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 use '#' as a separator in the frequency key?

Without a separator, frequency arrays [1,11] and [11,1] might serialize to the same string depending on join behavior. '#' guarantees each slot is distinct: '1#11#...' vs '11#1#...' are different.

When is the sort-key approach better?

When strings are short (k is small), sorting is simpler and the log k overhead is negligible. The frequency approach pays off only when strings are long.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →