49. Group Anagrams

At a Glance

• Topic: arrays-hashing
• Pattern: Hash Map Bucketing
• Difficulty: Medium
• Companies: Amazon, Meta, Google, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 49

Problem (one-liner)

Given an array of strings words, group strings that are anagrams of each other. Return a list of groups; order of groups and strings inside each group is flexible unless specified.

Recognition Cues

• "Group anagrams", "same letters rearranged"
• Need a canonical key per equivalence class (sorted letters or character counts)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — compare every pair with sorted letters — O(n² · k log k) time — wasteful.
• Better — hash map keyed by sorted string — O(n · k log k) time / O(n · k) space.
• Optimal — bucket by count signature (length-26 array as key tuple or encoded string) — O(n · k) time / O(n · k) space where k is max word length.

Optimal Solution

Go

package main

import "fmt"

func groupAnagrams(words []string) [][]string {
	buckets := make(map[string][]string)
	for _, word := range words {
		counts := [26]int{}
		for _, character := range word {
			counts[character-'a']++
		}
		key := fmt.Sprintf("%v", counts)
		buckets[key] = append(buckets[key], word)
	}
	result := make([][]string, 0, len(buckets))
	for _, group := range buckets {
		result = append(result, group)
	}
	return result
}

JavaScript

function groupAnagrams(words) {
	const buckets = new Map();
	for (const word of words) {
		const counts = new Array(26).fill(0);
		for (const character of word) {
			counts[character.charCodeAt(0) - 97]++;
		}
		const key = counts.join('#');
		if (!buckets.has(key)) {
			buckets.set(key, []);
		}
		buckets.get(key).push(word);
	}
	return [...buckets.values()];
}

Walkthrough

Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"]

Invariant: words sharing the same multiset of letters share the same key and end in one bucket.

Edge Cases

• Empty string appears with other empties in one group.
• Single-character strings: each distinct letter is its own group unless duplicates.
• All words unique and not anagrams → one word per group.

Pitfalls

• Using sort on the whole list of words instead of per-word key.
• Forgetting Unicode — problem is typically lowercase English a–z.

Similar Problems

• 242. Valid Anagram — verify two multisets match.
• 001. Two Sum — map as grouping / lookup structure.
• 217. Contains Duplicate — hash structure for keys.

Variants

• Return largest group only.
• Sorted output within each group lexicographically.
• Case-insensitive or Unicode normalization.

Mind-Map Tags

#hashmap #strings #anagram #bucketing #canonical-key