Grouping by Key

Before we start

By the end of this page you will be able to:

• See that grouping problems are really about finding a "name" (signature) that all equivalent elements share.
• Explain out loud why you hash the signature, not the element itself.
• Recognise this pattern in anagram grouping, shifted-string grouping, and any "group by hidden property" problem.

Stop at every Pause & Think box.

Picture this first (no code yet)

The sorting code is the canonical form (or signature). The tray label is the hash map key. The filing action is map[signature].append(element). That's the entire Grouping by Key pattern.

The actual problem

Given a list of strings, group together all strings that are anagrams of each other. Return each group as a list.

input  : ["eat","tea","tan","ate","nat","bat"]
output : [["eat","tea","ate"], ["tan","nat"], ["bat"]]

"eat", "tea", "ate" are all anagrams — they have the same letters in different order. They belong in the same group.

First, the slow way (so you feel the pain)

Compare every pair of strings. Two strings are anagrams if, after sorting their characters, they become identical.

# O(n²) × O(k log k) — checking every pair
groups = []
used = [False] * len(strs)
for i in range(len(strs)):
    if used[i]: continue
    group = [strs[i]]
    for j in range(i+1, len(strs)):
        if not used[j] and sorted(strs[i]) == sorted(strs[j]):
            group.append(strs[j])
            used[j] = True
    groups.append(group)

For n=10,000 strings of average length k=10: ~50 million pair comparisons, each costing O(k log k). Painful.

The grouping approach is O(n × k log k) — one sort per string, one hash map insert. No pairwise comparisons at all.

The turning point

The key question: what do all anagrams of "eat" have in common?

Sort the characters: sorted("eat") = ['a','e','t'], sorted("tea") = ['a','e','t'], sorted("ate") = ['a','e','t']. All produce "aet". That's the canonical form — the sorting code.

Any two strings are anagrams if and only if their sorted-character form is identical. So: sort each string's characters → use the result as the hash map key → append the original string to that key's group.

The one idea to remember

The entire pattern is in three steps:

1. Choose the right signature for this problem.
2. Map each element to its signature.
3. Group by collecting all elements with the same signature.

Watch it happen, frame by frame

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

Signature = sorted characters joined as string.

"eat" → sorted = "aet" → groups={"aet": ["eat"]}
"tea" → sorted = "aet" → groups={"aet": ["eat","tea"]}
"tan" → sorted = "ant" → groups={"aet": [...], "ant": ["tan"]}
"ate" → sorted = "aet" → groups={"aet": ["eat","tea","ate"]}
"nat" → sorted = "ant" → groups={"aet": [...], "ant": ["tan","nat"]}
"bat" → sorted = "abt" → groups={"aet": [...], "ant": [...], "abt": ["bat"]}

Result: [["eat","tea","ate"], ["tan","nat"], ["bat"]]  ✅

"ab"  → "ab"  → group "ab":  ["ab"]
"ba"  → "ab"  → group "ab":  ["ab","ba"]
"abc" → "abc" → group "abc": ["abc"]
"bca" → "abc" → group "abc": ["abc","bca"]
"cab" → "abc" → group "abc": ["abc","bca","cab"]
"a"   → "a"   → group "a":   ["a"]

3 groups: [["ab","ba"], ["abc","bca","cab"], ["a"]]  ✅

Now, the code — line by line

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)          # signature → [list of strings]

    for s in strs:
        key = "".join(sorted(s))        # compute canonical form: sorted characters
        groups[key].append(s)           # file the original string under its signature

    return list(groups.values())        # return all groups

Mapping every line to the post office:

• groups = defaultdict(list) — a set of empty trays, one created automatically when needed.
• key = "".join(sorted(s)) — compute the sorting code: sort the envelope address.
• groups[key].append(s) — drop the original letter into the tray for this code.
• return list(groups.values()) — hand over all the sorted trays.

Time: O(n × k log k) — n strings, each sorted in O(k log k). Space: O(n × k) — storing all strings in the groups.

Can we do better than O(k log k) per string? Yes — use a character frequency tuple as the key:

def groupAnagrams_linear(strs):
    groups = defaultdict(list)

    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        key = tuple(count)              # (1,0,0,...,1,0,...,1,...) — O(k) to compute
        groups[key].append(s)

    return list(groups.values())

Now each key is computed in O(k) — better for long strings with large k.

Why does the canonical form always work?

The canonical form must have one property: two elements produce the same canonical form if and only if they are equivalent. For anagrams, sorted characters satisfies this:

• Sorted characters of two anagrams are always identical (same letters, now in the same order). ✓
• If two strings have identical sorted characters, they must be anagrams. ✓

So the canonical form is a perfect equivalence detector — it neither over-groups (non-anagrams never collide) nor under-groups (all anagrams always match).

When should I reach for this? (the trigger list)

Reach for grouping-by-signature when:

• You need to collect elements into equivalence classes — groups where all members share a hidden property.
• Two elements look different on the surface but are "the same" by some transformation (anagram, shifted, rotated, palindrome-normalised, etc.).
• The brute-force answer compares every pair to decide if they belong together — O(n²).
• You can describe the equivalence as: "elements A and B are equivalent if f(A) == f(B)" for some computable function f.

The choice of f (the signature function) is the entire design decision. Everything else is the same hash-map grouping code.

The same trick in four disguises

The skeleton is always:

groups = defaultdict(list)
for element in data:
    key = signature(element)    # ← only this line changes per problem
    groups[key].append(element)
return list(groups.values())

Disguise 1 — Group Shifted Strings (LC #249)

Two strings are "shifted" equivalents if one can become the other by shifting all characters by the same amount (circular). Canonical form: normalise to start from 'a' by subtracting the first character's value.

def groupStrings(strings):
    groups = defaultdict(list)
    for s in strings:
        # Shift so first char becomes 'a'
        shift = ord(s[0]) - ord('a')
        key = tuple((ord(ch) - ord('a') - shift) % 26 for ch in s)
        groups[key].append(s)
    return list(groups.values())

"abc" → (0,1,2). "bcd" → (0,1,2). Same key → same group. ✓

Disguise 2 — Find Duplicate File in System (LC #609)

Two files are duplicates if their content is identical. Canonical form = the file content string itself.

def findDuplicate(paths):
    content_map = defaultdict(list)
    for path in paths:
        parts = path.split()
        directory = parts[0]
        for file_info in parts[1:]:
            name, content = file_info.split('(')
            content = content[:-1]               # remove trailing ')'
            content_map[content].append(directory + '/' + name)
    return [group for group in content_map.values() if len(group) > 1]

Disguise 3 — Isomorphic Strings / Isomorphic Groups

Two strings are isomorphic if there's a consistent character mapping from one to the other. Canonical form: replace each character with its first-occurrence index.

def canonicalForm(s):
    mapping = {}
    result = []
    counter = 0
    for ch in s:
        if ch not in mapping:
            mapping[ch] = counter
            counter += 1
        result.append(mapping[ch])
    return tuple(result)

# "egg" → (0,1,1),  "add" → (0,1,1)  → same group
# "foo" → (0,1,1),  "bar" → (0,1,2)  → different groups

Disguise 4 — Group by Row in Spiral / BFS level

In tree/graph problems, group nodes by their level (BFS) or by a computed coordinate. Same skeleton: compute the "address" (level, coordinate), group by it.

Traps that catch beginners

Say it like a pro (interview one-liner)

"This is a grouping-by-canonical-form problem. I'll compute a signature for each element — one that's identical for equivalent elements and different otherwise — then use the signature as a hash map key and collect all elements with the same key into a list. One pass, O(n) groups built. The only design choice is the right signature function."

groups = defaultdict(list)
for element in data:
    key = canonical_form(element)   # same for equivalent elements, different otherwise
    groups[key].append(element)
return list(groups.values())

Check yourself

key = min(s[i:] + s[:i] for i in range(len(s)))

Practice problems

That's the core of the Hashing chapter's grouping pattern. Next up: Hashing for Subarray Problems — where the hash map stores prefix sums to count subarrays satisfying a condition in a single pass.