Group Anagrams

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

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. Convert the count array into a unique key (e.g., with separators).
3. Append the string to the group for that key.
4. Return all groups.

Correctness sketch

• Invariant: all strings with identical signatures belong to the same group.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

Trace (hand walkthrough)

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

Walk:
- sort keys: eat/tea/ate -> "aet" group
- tan/nat -> "ant" group
- bat -> "abt" group

Pitfalls to avoid

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

Complexity

• Time: O(total characters)
• Extra space: O(total characters).

Implementation notes (Go)

• Use a sorted string or 26-count signature as the key.
• For count keys, build with a strings.Builder to avoid allocations.