Group Anagrams

Given a list of strings, group the anagrams together. Return any order of groups.

Why this is worth learning

A key should represent the equivalence class, not an accidental property such as total letter sum. Correct canonicalization makes grouping straightforward.

Before coding: one-minute experiment

Why must the two empty strings in ["", "", "a"] remain two entries in one group?

Function signature

func GroupAnagrams(strs []string) [][]string

Inputs / outputs

• strs: slice of lowercase strings.
• Return: groups of anagrams.

Example

strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

Constraints

• 0 <= len(strs) <= 100_000
• Each string length <= 100
• Strings contain only lowercase letters.

Core idea (near-solution)

Anagrams share the same character count signature. Use a 26-count key for each string and group by that key.

Invariant: all strings with identical signatures belong to the same group.

Algorithm (step-by-step)

1. For each string, build a 26-count array.
2. Use the [26]int array directly as the map key; Go arrays of comparable elements are comparable.
3. Append the string to the group for that key.
4. Return all groups.

Correctness sketch

The 26 counts uniquely describe a lowercase string's multiset. The reference uses the complete [26]int array as its key, so equality checks every coordinate; it does not compress counts into a checksum or ambiguous string. Two strings have equal keys exactly when every count agrees, which is exactly anagram equivalence. Appending each input occurrence to its key's group therefore places all and only mutual anagrams together. Every occurrence is appended once, including duplicate and empty strings, so the output preserves input multiplicity. Iterating the group map may reorder groups but cannot change their membership.

Trace (hand walkthrough)

Example input:
strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

Walk:
- eat/tea/ate each give counts a=1,e=1,t=1 (all other entries zero)
- tan/nat each give counts a=1,n=1,t=1: a different key
- bat gives counts a=1,b=1,t=1: a third key
- append every occurrence; the outer map order is not specified

Pitfalls to avoid

• Using a key that can collide (must separate counts clearly).
• Forgetting that empty strings are valid and should be grouped.

Debugging lens

Test repeated inputs, empty strings, and keys whose digit counts could collide without separators. Normalize group order for comparison; do not drop duplicate strings.

Complexity

Let N be the number of strings and C their total byte length. Expected time: O(N+C), including construction of all 26-count keys even for empty strings. Auxiliary map/key storage: O(N) under the fixed alphabet and length bound; output stores O(N) string references. It need not copy all C input bytes.

Implementation notes (Go)

• Use a sorted string or 26-count signature as the key.
• [26]int works as a map key; []int does not. The fixed-array key avoids decimal serialization and delimiter rules entirely.

Reconstruction checkpoint

Why must the two empty strings in ["", "", "a"] remain two entries in one group?

Return to Hash Map · Module quiz