Medium

Given a list of words strs, group the words that are anagrams of one another (the same letters in a different order). Return the groups as a list of lists. To make the answer unique: sort each group ascending, then sort the groups by their first word. An empty input gives an empty list.

`strs`	result	why
`["eat", "tea", "tan", "ate", "nat", "bat"]`	`[["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]`	groups ordered `ate` < `bat` < `nat`
`["abc", "xyz", "bca", "abc"]`	`[["abc", "abc", "bca"], ["xyz"]]`	duplicates stay in one group
`[""]`	`[[""]]`	the empty word is its own group
`[]`	`[]`

Two words are anagrams exactly when they have the same canonical key. Two common keys: the word's letters sorted ("eat" → "aet", costs $O(k \log k)$ per word of length $k$ ), or a count of each of the 26 letters ("eat" → 26 counts, $O(k)$ , and the count tuple/array is itself the key). Put each word into a hash map keyed that way; every bucket is one group. Finish by sorting inside each bucket and sorting the buckets by their first word so the output is deterministic.

Python

def group_anagrams(strs):
    """Group the words that are anagrams of each other (same letters, any order).
    Return a list of groups: each group sorted ascending, and the groups sorted
    by their first word."""
    groups = {}  # sorted-letters key -> words made of exactly those letters
    for word in strs:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # Fix the output order so it is deterministic: inside each group, then by first word.
    result = [sorted(group) for group in groups.values()]
    result.sort(key=lambda group: group[0])
    return result

Group Anagrams

Longest Substring Without Repeating Characters