Group Anagrams

Classify once. Group by identity.

A useful Group Anagrams solution does not compare every string with every existing group. It assigns each string a stable identity based on its character composition, then lets a hash map collect strings with equal identities.

For the stated lowercase-English-letter constraint, use a 26-element frequency tuple as the key:

1. Count each letter in the current string.
2. Freeze the count list as a tuple.
3. Use that tuple to find a bucket in a hash map.
4. Append the original string to the bucket.

Sorting each string is the simplest baseline. Counting characters is the sharper solution because anagram membership depends on frequencies, not order.

The Contract and the Key Idea

The input is an array of strings. The output is a collection of groups such that strings in the same group are anagrams. The order of the groups and the order within each group may be arbitrary.

The problem’s constraints provide the representation boundary:

• There can be up to 10^4 strings.
• Each string can have length from 0 to 100.
• Every character is a lowercase English letter.

Two strings are anagrams exactly when every character occurs the same number of times in both strings. Character order is irrelevant; frequency is the deciding property.

For example, "eat" and "tea" each contain one a, one e, and one t, so they need the same key. "tan" has a different frequency profile and belongs elsewhere.

The map has a simple shape:

frequency key -> list of original strings

The key classifies. The value preserves the output. The dictionary is not the clever part. The key is.

Recognize Classification, Not Pair Search

The important signal is the phrase group together.

When a problem asks you to group items by a shared property, look for an equivalence-class representation: a key whose equality means “belongs in the same group.” Once that key exists, the algorithm becomes:

compute key
look up bucket
append item

A brute-force design might compare each pair of strings, count their characters, and merge matching groups. That repeats classification work. A keyed design computes each string’s identity once and uses the dictionary to route it.

This is the Arrays & Hashing pattern, but the lookup question is different from a pair-sum problem. Here, the key does not find a complement or merely record membership. It names an entire class of equivalent strings.

Baseline: Sort Each String

The most direct canonical key is the sorted version of the string.

For every string:

1. Sort its characters.
2. Use the sorted result as the dictionary key.
3. Append the original string to that key’s bucket.

For the input below, anagrams collapse to the same sorted key:

["eat", "tea", "tan", "ate", "nat", "bat"]

Original string	Sorted key
"eat"	"aet"
"tea"	"aet"
"tan"	"ant"
"ate"	"aet"
"nat"	"ant"
"bat"	"abt"

The buckets become:

["eat", "tea", "ate"]
["tan", "nat"]
["bat"]

Store the original strings. The sorted string is classification state, not the requested output.

If N is the number of strings and K is the maximum string length, sorting each string costs O(K log K), giving a total of O(NK log K). This is a strong baseline: easy to derive, easy to verify, and valid under the contract. I prefer stating it before optimizing because a baseline gives you something concrete to improve.

Frequency Vectors as Canonical Keys

Sorting works, but it processes character order even though order has no bearing on anagram membership. The fixed lowercase alphabet gives us a better representation.

Create a 26-slot count list. Slot 0 represents a, slot 1 represents b, and slot 25 represents z.

For "eat", increment the slots for e, a, and t. The resulting vector has a 1 at those three positions and zeroes elsewhere. "tea" and "ate" produce the same vector because they contain the same letters with the same frequencies.

That vector is the canonical identity. This is how to group strings by character count: equal count profiles go to the same bucket.

Python lists are mutable and cannot be dictionary keys, so freeze the count list:

key = tuple(counts)

The tuple is a stable snapshot of the 26 counts.

Key	Cost per string	Advantage	Boundary
Sorted string	O(K log K)	Simple and naturally handles a broader character set	Sorts information we do not need
Frequency tuple	O(K + 26)	Avoids sorting under the fixed alphabet	Assumes lowercase English letters

Because 26 is fixed, the frequency approach costs O(K) per string and O(NK) overall.

A tuple is safer than casually concatenating counts into text. Positional slots preserve both the count and its boundary, so the key has an unambiguous meaning.

Invariant and Correctness Proof

Give the map a precise meaning before writing the loop:

After processing any prefix of the input, each dictionary entry contains exactly the processed original strings whose frequency tuple equals that entry’s key.

That is the loop invariant.

Why anagrams share a key

An anagram rearranges characters without changing how many times each character appears. Therefore, two anagrams have matching counts for a, matching counts for b, and so on through z. Their 26-element tuples are equal, so the algorithm sends them to the same bucket.

Why equal keys cannot merge non-anagrams

If two strings have equal frequency tuples, every lowercase character appears equally often in both. They contain the same multiset of characters, so one can be rearranged into the other. They are anagrams.

Both directions hold:

anagrams -> equal keys
equal keys -> anagrams

The dictionary only groups equal keys, so it cannot merge strings from different anagram classes. Hashing makes bucket lookup efficient; the frequency representation establishes why the grouping is correct.

Trace the Map State

Use the standard example and focus on the state transition rather than printing all 26 positions repeatedly.

Input	Key description	Action	Bucket state
"eat"	one a, one e, one t	Create key	["eat"]
"tea"	one a, one e, one t	Reuse key	["eat", "tea"]
"tan"	one a, one n, one t	Create key	["tan"]
"ate"	one a, one e, one t	Reuse key	["eat", "tea", "ate"]
"nat"	one a, one n, one t	Reuse key	["tan", "nat"]
"bat"	one a, one b, one t	Create key	["bat"]

There are only two meaningful transitions:

• A new tuple creates a bucket.
• An existing tuple reuses its bucket.

The empty string needs no special branch. Its key is the all-zero tuple, so all empty strings join the same group. Duplicate strings also append to the same bucket naturally.

Implement the Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for s in strs:
            counts = [0] * 26

            for c in s:
                index = ord(c) - ord("a")
                counts[index] += 1

            key = tuple(counts)
            groups[key].append(s)

        return list(groups.values())

Each variable has one obligation:

• counts records the frequency of each lowercase letter.
• key freezes that frequency state for dictionary lookup.
• groups[key] stores the original strings with that identity.
• list(groups.values()) removes the map keys from the returned result.

ord(c) - ord("a") maps lowercase letters to positions 0 through 25. That mapping is valid only because the input contract restricts the alphabet. If the character requirements changed, the key representation would need to change too.

Create counts inside the outer loop. If you create it once outside the loop, later strings inherit earlier counts. That turns the key into accumulated history instead of the current string’s identity.

Complexity and Edge Cases

Let N be the number of strings and K the maximum string length.

Counting each string costs O(K) in the worst case. Converting the list to a tuple costs O(26), so the total is:

O(N(K + 26)) = O(NK)

This treats dictionary operations as average O(1), the usual hash-table assumption.

Space has two useful views:

• The output contains the original strings, so output-related storage is O(NK) when string contents are counted.
• The map can have up to N keys and buckets. Each frequency tuple has fixed size 26, so the auxiliary grouping structure is O(N) under this contract.

Including the returned grouping, total space is commonly reported as O(NK).

Check these boundaries:

• Empty strings: they share the all-zero tuple.
• Duplicate strings: they append to one bucket.
• All unique strings: each creates a bucket.
• All anagrams: every string reuses one bucket.
• Different lengths: their frequency totals differ, so they cannot share a key unless both are empty.
• A changed alphabet: a 26-slot vector is no longer sufficient for characters outside a through z.

The fixed alphabet is the decision boundary. Under this contract, frequency counting is the clean optimization. For a broader character set, a sorted-string key generalizes more naturally, or you can define a character-to-count representation that explicitly covers the domain.

The Transferable Pattern

When a problem asks you to group items by an order-insensitive property, do not begin by comparing every item with every other item. Ask:

What canonical representation has equal keys exactly when the items belong to the same class?

For anagrams, the answer can be a sorted string or a character-frequency tuple. Sorting is the dependable baseline. The frequency tuple removes unnecessary sorting because the fixed alphabet makes counts sufficient.

The next time you see this pattern:

1. State the property that defines group membership.
2. Derive a canonical key for that property.
3. Prove key equality in both directions.
4. Aggregate equal keys in a hash map.
5. Test the boundaries where the representation could fail.

Name the key. State the invariant. Prove both directions. Then write the bucket update. That is the reusable skill: classify once, group by identity.