Group Anagrams

MEDIUM✓ CHIP-TIMEDLC #49 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Bundle the words that are anagrams of each other — same letters, shuffled — into groups; every word lands in exactly one group.

A list of lowercase strings arrives, and the task is to bundle together every string that is a letter-for-letter rearrangement of another — same letters, same counts, just shuffled.

Every string in the input must land in exactly one group; a string with no anagram partners still forms its own group of one, standing alone.

The order of the groups in the output, and the order of strings within each group, is free — grouping correctly is what's judged, not any particular arrangement.

the list can hold up to a few thousand strings
each string is lowercase letters only, generally short
empty strings are allowed and group with each other
group order and within-group order are both unconstrained

EX 01

strs = ["listen", "silent", "enlist", "tea", "ate", "car"]

→ [["listen", "silent", "enlist"], ["tea", "ate"], ["car"]]

EX 02

strs = [""]

→ [[""]]

EX 03

strs = ["a"]

→ [["a"]]

The hintstake only what you need

HINT 1 THE NUDGE

Two words belong together exactly when some fingerprint of theirs matches. What fingerprint survives shuffling?

HINT 2 THE STRUCTURE

Sorting a word’s letters gives a canonical form — every anagram sorts to the same string. A map from canonical form to bucket does the grouping.

HINT 3 ONE STEP FROM THE ANSWER

Sorting each word costs k·log k. Letters are only 26: a count-of-each-letter signature is the same key in O(k) — tuple it in Python, join it into a string in Java.

Coach's boardthe pattern, step by step

THE FINGERPRINT SORTPATTERN · LETTER-COUNT KEYstrs = ["ab", "ba", "abc"]

abc

BUCKETS — LETTER-COUNT KEY → WORDS

— empty —

STEP 1

Three words: ab, ba, abc. Each gets fingerprinted by its letter counts — same fingerprint, same group.

STEP 1 / 8 · ← → WORK TOO

The splitstwo paces, two languages

grind/group-anagrams.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for w in strs:
            counts = [0] * 26
            for ch in w:
                counts[ord(ch) - ord("a")] += 1
            groups.setdefault(tuple(counts), []).append(w)
        return list(groups.values())

TIME O(N·K)SPACE O(N·K)PYTHON · RACE PACE · 9 LN

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for w in strs:
            key = "".join(sorted(w))
            groups.setdefault(key, []).append(w)
        return list(groups.values())

TIME O(N·K LOG K)SPACE O(N·K)PYTHON · TRAINING PACE · 7 LN

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : strs) {
            int[] counts = new int[26];
            for (char ch : w.toCharArray()) {
                counts[ch - 'a']++;
            }
            StringBuilder key = new StringBuilder();
            for (int c : counts) {
                key.append(c).append('#');
            }
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }
}

TIME O(N·K)SPACE O(N·K)JAVA · RACE PACE · 17 LN

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : strs) {
            char[] letters = w.toCharArray();
            Arrays.sort(letters);
            groups.computeIfAbsent(new String(letters), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }
}

TIME O(N·K LOG K)SPACE O(N·K)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED