Anagrams

Solve the group-anagrams interview problem two ways: a sort-key approach and a frequency-count key approach, both powered by Map.

5 min read Level 2/5 #dsa#hashing#anagram

What you'll learn

Implement group anagrams using a sorted string as the Map key
Implement group anagrams using a frequency-count string key to avoid sorting
Compare the time complexity of both approaches

The group-anagrams problem is a staple in coding interviews: given an array of strings, return arrays of strings that are anagrams of each other. Two strings are anagrams when they contain exactly the same characters in the same frequencies, regardless of order.

Example input: ["eat","tea","tan","ate","nat","bat"] Expected output: [["eat","tea","ate"],["tan","nat"],["bat"]]

Strategy 1 — Sorted-String Key

Sort each word’s characters alphabetically. Anagrams will always produce the same sorted string, so we use that as the Map key.

function groupAnagramsSort(words) {
  const groups = new Map();

  for (const word of words) {
    const key = [...word].sort().join(""); // "eat" → "aet"
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }

  return [...groups.values()];
}

const input = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagramsSort(input));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Each word of length m costs O(m log m) to sort. For n words the total is O(n · m log m).

Strategy 2 — Frequency-Count Key

Instead of sorting, encode each word as a character-count string. Because the 26 lowercase-letter counts are fixed-length, the key length is constant (O(1) to compare) and building it is O(m) — no sorting needed.

function groupAnagramsCount(words) {
  const groups = new Map();

  for (const word of words) {
    // Build a 26-element count array for 'a'-'z'
    const counts = new Array(26).fill(0);
    for (const ch of word) {
      counts[ch.charCodeAt(0) - 97]++;
    }
    // Serialise to a string key, e.g. "1,0,0,...,1,0,...,0"
    const key = counts.join(",");

    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }

  return [...groups.values()];
}

console.log(groupAnagramsCount(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Total time: O(n · m) where m is the maximum word length.

Which Strategy to Choose?

Approach	Time per word	Total time	Works for non-ASCII?
Sort key	O(m log m)	O(n · m log m)	Yes (with localeCompare)
Count key	O(m)	O(n · m)	Only for fixed alphabet

For pure lowercase-ASCII inputs the count-key approach is asymptotically faster. When inputs can contain Unicode or an open alphabet, the sort-key approach is simpler and more robust.

Detecting a Single Anagram Pair

If you only need to check whether two individual strings are anagrams (not group many), the early-exit version from the previous lesson is most efficient:

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const freq = new Map();
  for (const ch of a) freq.set(ch, (freq.get(ch) ?? 0) + 1);
  for (const ch of b) {
    const n = freq.get(ch);
    if (!n) return false;
    n === 1 ? freq.delete(ch) : freq.set(ch, n - 1);
  }
  return freq.size === 0;
}

console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car"));         // false

Up Next

See how Map’s insertion-order guarantee enables an elegant O(1) LRU cache implementation.

LRU Cache →