Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Hashing

Guide 2 of 6 · Path 2 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumhashing

Group Anagrams

Problem (restated)

Given an array of strings, group the anagrams together. Order of groups and order inside a group can be anything.

Intuition

Anagrams share a signature: sorted characters, or a 26-count tuple. Hash map signature → list of words.

Approaches

Hash map with sorted key

Tested only
Time O(n · k log k)Space O(n · k)

Idea. For each word, key = sorted(word). Append word to map[key].

Walkthrough. [“eat”,“tea”,“tan”,“ate”] → keys “aet” groups eat/tea/ate; “ant” groups tan.

Trade-offs. Simple. Count-array key is O(n·k) and faster when k is large.

Solution
export function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = [...s].sort().join("");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

export function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = [...s].sort().join("");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

Hash map with count signature

Tested only
Time O(n · k)Space O(n · k)

Idea. Key from 26 letter counts joined as a string (or tuple).

Walkthrough. Same grouping, linear in total characters.

Trade-offs. Better asymptotics for long strings; slightly more code.

Solution
export function groupAnagramsCount(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const cnt = new Array(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    const key = cnt.join("#");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

export function groupAnagramsCount(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const cnt = new Array(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    const key = cnt.join("#");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

Template connection

groupByKey from the Hashing template. key is the anagram signature.

Reflection