Group Anagrams

Problem

A search engine needs to cluster query variations so that synonymous rearrangements map to the same result page. Given an array of strings, group all strings that are anagrams of each other. Each group can appear in any order.

Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
 
Input: [""]      → [[""]]
Input: ["a"]     → [["a"]]

Solution

Approach: grouping by a canonical derived key.

The insight is that anagrams are the same multiset of characters in a different order, so sorting a word's characters produces a value that is identical for every anagram of it and different for everything else. That sorted form is the canonical key. Build a defaultdict(list), then for each word compute key = tuple(sorted(word)) and append the word to groups[key]. Words that are anagrams collide onto the same key on purpose and accumulate in the same list; list(groups.values()) returns those lists as the grouped output. One pass over the input groups everything - no pairwise comparison of words.

The key must be tuple(sorted(word)) rather than the list sorted(word) because dict keys must be hashable and lists are not, while tuples are. defaultdict(list) creates the empty list automatically on first access to a new key, so the loop body never special-cases the first word in a group. Trace ["eat","tea","bat"]: "eat" sorts to ('a','e','t') and starts a bucket; "tea" sorts to the same tuple and joins it; "bat" sorts to ('a','b','t'), a new key, so it gets its own bucket. The result is [["eat","tea"], ["bat"]].

Edge cases: a single word forms a one-element group; multiple empty strings all sort to () and land in one group; words with no anagrams each become their own singleton list.

Complexity: O(n * k log k) time, O(n * k) space - n words, each sorted in O(k log k) for length k; all words plus their keys are stored.