group-anagrams.ts

/**
 * 49. Group Anagrams  (Medium)
 * Link: https://leetcode.com/problems/group-anagrams/
 *
 * Given an array of strings, group the anagrams together. The order of the
 * groups and of the strings within a group does not matter.
 *
 * Example:
 *   Input:  ["eat","tea","tan","ate","nat","bat"]
 *   Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
 *
 * Approach:
 *   Anagrams share the same 26-letter frequency signature. Build a key from the
 *   per-letter counts (cheaper and more robust than sorting for long words) and
 *   bucket each word under its key in a map.
 *
 * Time:  O(n * k)  — n words, k = max word length (to build each key).
 * Space: O(n * k)  — all words stored across the buckets.
 */
export function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();

  for (const word of strs) {
    const counts = new Array(26).fill(0);
    for (const ch of word) {
      counts[ch.charCodeAt(0) - 97]++;
    }
    const key = counts.join("#");

    const bucket = groups.get(key);
    if (bucket) {
      bucket.push(word);
    } else {
      groups.set(key, [word]);
    }
  }

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