Group Anagrams

Problem

Given a list of strings, gather them into groups where every string in a group is an anagram of the others — i.e. they use exactly the same multiset of letters, just in a different order. Return the groups as a list of lists; the order of groups and the order within a group don’t matter.

All strings consist of lowercase English letters.

Examples

Example 1: strs = ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]] “eat”, “tea”, “ate” all rearrange the letters {a,e,t}; “tan”/“nat” share {a,n,t}; “bat” is alone.

Example 2: strs = [""] → [[""]] A single empty string forms its own group.

Example 3: strs = ["a"] → [["a"]] One string, one group.

Constraints

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• Lowercase English letters only.

With up to 10^4 strings, comparing every pair (~10^8 string comparisons) is too slow — you need a per-string signature, not pairwise checks.

Think about it first

TL;DR

Hash map keyed by a canonical signature (sorted string, or 26-count tuple) — O(n·k) time, O(n·k) space (n strings of length ≤ k).

Approach 1 — Brute force (pairwise comparison)

Repeatedly take an ungrouped string, then scan the remaining strings and pull in every one that is its anagram (same Counter).

from typing import List
from collections import Counter


def groupAnagrams(strs: List[str]) -> List[List[str]]:
    used = [False] * len(strs)
    groups: List[List[str]] = []
    for i, word in enumerate(strs):
        if used[i]:
            continue
        group = [word]
        used[i] = True
        target = Counter(word)
        for j in range(i + 1, len(strs)):
            if not used[j] and Counter(strs[j]) == target:
                group.append(strs[j])
                used[j] = True
        groups.append(group)
    return groups

Complexity: O(n²·k) time (every pair, each comparison O(k)), O(n·k) space. With n = 10^4 and k = 100 that is ~10^10 character operations — far past the limit.

Approach 2 — Hash map keyed by sorted string

Two strings are anagrams iff sorting their characters yields the identical string. So sorted(word) is a canonical form: use it as a dictionary key and grouping becomes a single pass.

from typing import List
from collections import defaultdict


def groupAnagrams(strs: List[str]) -> List[List[str]]:
    buckets: defaultdict[str, List[str]] = defaultdict(list)
    for word in strs:
        key = "".join(sorted(word))
        buckets[key].append(word)
    return list(buckets.values())

Walkthrough on Example 1, ["eat","tea","tan","ate","nat","bat"]:

The dict values are exactly the expected groups.

Complexity: O(n·k·log k) time (sorting each string), O(n·k) space.

Approach 3 — Hash map keyed by letter-count vector

The canonical form need not be sorted text. The histogram of the 26 letters identifies an anagram class just as uniquely, and building it is O(k) instead of O(k log k). This is the counting-sort idea (tallying occurrences over a small fixed alphabet) applied to key construction.

from typing import List, Tuple
from collections import defaultdict


def groupAnagrams(strs: List[str]) -> List[List[str]]:
    buckets: defaultdict[Tuple[int, ...], List[str]] = defaultdict(list)
    for word in strs:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - ord("a")] += 1
        buckets[tuple(counts)].append(word)
    return list(buckets.values())

Walkthrough on Example 1: “eat”, “tea”, “ate” each produce a vector with a=1, e=1, t=1 and zeros elsewhere — the identical 26-tuple — so all three land in one bucket; “tan”/“nat” share the a=1, n=1, t=1 tuple; “bat” gets its own. Same three groups as before.

Complexity: O(n·k) time, O(n·k) space (each key is a fixed 26-tuple, so keys add O(26·n) = O(n)).

In practice the sorted-string version often runs comparably fast for short strings (Python’s sorted runs in C); the count-tuple version wins asymptotically and drops the log factor.

Common pitfalls

• Using a list as the dict key — lists are unhashable; convert the count vector to a tuple (or join sorted chars into a str).
• Trying to hash Counter objects directly — also unhashable.
• Summing character codes or multiplying primes as a “hash” — collisions (or overflow reasoning) make this fragile; use the full canonical form.
• Forgetting that the empty string is a valid input — it needs its own bucket, which both approaches handle naturally.

Pattern takeaway

To group items by an equivalence relation (“is an anagram of”), don’t compare items pairwise — design a canonical key such that two items are equivalent iff their keys are equal, then bucket with one hash-map pass. Choosing the cheapest computable canonical form (count vector vs. sorted copy) is where the final complexity is won.