Group Anagrams

PracticeNeetCode ↗LeetCode ↗

Given an array of strings strs, group the anagrams together. The order of the groups and the order within a group don't matter.

Example

Key Pointers

• Anagrams share the same letter-count signature — build that signature instead of sorting each string, to skip the extra O(k log k) sort cost.
• A 26-length count array converted to a tuple is hashable, so it works directly as a dictionary key.
• Group first, worry about order later — the result only needs the anagram sets, not a particular ordering.

Step-by-Step Analysis

1. Create a hashmap groups: signature → list of strings.
2. For each string s, build a 26-length count array of its letters.
3. Convert the array to a tuple and use it as the key in groups, appending s to that key's list.
4. Return all the lists (groups.values()) once every string has been processed.

Complexity

Time: O(n · k) where k is the max string length — Space: O(n · k)

Code

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

Code Explanation

How the solution above works, piece by piece.

1. groups = defaultdict(list): key → list of words. defaultdict creates an empty list the first time a key is used.
2. For each word, build count = [0] * 26, one slot per letter, and add 1 for every character (ord(ch) - ord('a') gives the slot).
3. tuple(count): lists can't be dictionary keys, tuples can. Two words are anagrams exactly when their tuples are equal.
4. groups[key].append(s) puts the word into its group.
5. list(groups.values()) returns the groups. O(n · k) for n words of length k, faster than sorting each word (O(n · k log k)).

Visual Walkthrough

Running it on strs = ["eat", "tea", "tan", "ate", "nat", "bat"]:

Video Explanation

NeetCode — Group Anagrams, LeetCode 49