Group Anagrams: using sorted strings as bucket keys

Valid Anagram was a yes/no question. Group Anagrams is the same idea turned into a bucketing problem: for every string in the input, compute a key that is identical for all its anagrams, then drop it in the right bucket. No string ever gets compared to another. One map, one pass.

What the constraints are telling you

The input is up to 10,000 strings, each up to 100 characters, all lowercase English letters. Three things fall out of this immediately.

First, n = 10⁴ rules out anything quadratic. A nested scan — checking each new string against every existing group — would hit 10⁸ operations in the worst case and blow the time limit. You need O(n) or O(n · something small).

Second, strings are short (m ≤ 100) and the alphabet is bounded (26 characters). Both these facts make character-counting cheap. Sorting 100 characters costs 100 · log(100) ≈ 700 comparisons. Building a 26-element frequency array costs exactly 100 increments. Neither is expensive.

Third, the lowercase-only constraint means you can use a fixed-size integer array as a key instead of a dictionary. That's the basis for the frequency-tuple approach described later.

The brute force: O(n² · m log m)

The obvious approach: for each new string, scan all previously built groups. If the first element of any group is an anagram of the current string, add the current string to that group. If no group matches, start a new one.

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        result: list[list[str]] = []
        for s in strs:
            placed = False
            for group in result:
                if sorted(s) == sorted(group[0]):
                    group.append(s)
                    placed = True
                    break
            if not placed:
                result.append([s])
        return result

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var result = new List<IList<string>>();
        foreach (string s in strs) {
            bool placed = false;
            char[] sChars = s.ToCharArray();
            Array.Sort(sChars);
            foreach (var group in result) {
                char[] g0Chars = group[0].ToCharArray();
                Array.Sort(g0Chars);
                if (new string(sChars) == new string(g0Chars)) {
                    group.Add(s);
                    placed = true;
                    break;
                }
            }
            if (!placed)
                result.Add(new List<string> { s });
        }
        return result;
    }
}

Walk through ["eat","tea","tan","ate","nat","bat"] step by step to see where this breaks down:

• "eat": no groups yet. New group: [["eat"]].
• "tea": check group[0] representative "eat". Sort both -> "aet" == "aet". Add to group 0: [["eat","tea"]].
• "tan": check group 0 representative "eat" -> "ant" != "aet". No match. New group: [["eat","tea"],["tan"]].
• "ate": check group 0 -> "aet" == "aet". Match: [["eat","tea","ate"],["tan"]].
• "nat": check group 0 -> "ant" != "aet". Check group 1 -> "ant" == "ant". Match: [["eat","tea","ate"],["tan","nat"]].
• "bat": check group 0 -> miss. Check group 1 -> miss. New group: [["eat","tea","ate"],["tan","nat"],["bat"]].

Correct output. But in the worst case — 10,000 strings that are all distinct non-anagrams — you check string k against k-1 groups. That gives 0 + 1 + 2 + ... + (n-1) = O(n²) group comparisons, each costing O(m log m) to sort. At n = 10⁴ and m = 100, that is 10¹⁰ character operations. Way too slow.

The sorted-key approach: O(n · m log m)

The hash map eliminates the scan entirely. Instead of checking existing groups one by one, you compute a key for the current string and let the map route you to the right bucket in O(m) time.

The core insight: two strings are anagrams when, and only when, they sort to the same sequence. "eat", "tea", and "ate" all sort to "aet". Use that sorted string as the bucket key.

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

Here is the same example traced step by step through the map:

"eat" -> sorted -> "aet" -> buckets = {"aet": ["eat"]}
"tea" -> sorted -> "aet" -> buckets = {"aet": ["eat","tea"]}
"tan" -> sorted -> "ant" -> buckets = {"aet": ["eat","tea"], "ant": ["tan"]}
"ate" -> sorted -> "aet" -> buckets = {"aet": ["eat","tea","ate"], "ant": ["tan"]}
"nat" -> sorted -> "ant" -> buckets = {"aet": ["eat","tea","ate"], "ant": ["tan","nat"]}
"bat" -> sorted -> "abt" -> buckets = {"aet": [...], "ant": [...], "abt": ["bat"]}

One lookup per string. No iteration over existing groups.

The flow for any single string looks like this:

setdefault is the cleanest Python idiom here. It returns the existing list if the key is present, inserts an empty list and returns it if not — one call instead of the usual if key in dict dance. defaultdict(list) is equally idiomatic:

from collections import defaultdict
 
class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        buckets: defaultdict[str, list[str]] = defaultdict(list)
        for s in strs:
            buckets["".join(sorted(s))].append(s)
        return list(buckets.values())

I reach for defaultdict when building grouped structures in production code. setdefault in a tight loop has a slight overhead because it constructs the default value even when the key already exists; defaultdict does not. The difference is negligible at 10⁴ strings, but it is worth knowing.

The C# equivalent:

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var buckets = new Dictionary<string, List<string>>();
        foreach (string s in strs) {
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);
            if (!buckets.TryGetValue(key, out var group)) {
                group = new List<string>();
                buckets[key] = group;
            }
            group.Add(s);
        }
        return buckets.Values.Cast<IList<string>>().ToList();
    }
}

The Cast<IList<string>>().ToList() on the last line is a minor annoyance: Dictionary<string, List<string>>.Values gives you ICollection<List<string>>, but the return type is IList<IList<string>>. The cast is necessary because C# does not infer covariance for generic collections. It allocates a new list of interface references — O(k) where k is the number of distinct anagram groups — which is fine.

The frequency-tuple key: O(n · m)

Instead of sorting, build the 26-element frequency array from Valid Anagram and use it as a key:

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        buckets: dict[tuple[int, ...], list[str]] = {}
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            key = tuple(count)
            buckets.setdefault(key, []).append(s)
        return list(buckets.values())

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var buckets = new Dictionary<string, List<string>>();
        foreach (string s in strs) {
            int[] count = new int[26];
            foreach (char c in s) {
                count[c - 'a']++;
            }
            string key = string.Join(",", count);
            if (!buckets.TryGetValue(key, out var group)) {
                group = new List<string>();
                buckets[key] = group;
            }
            group.Add(s);
        }
        return buckets.Values.Cast<IList<string>>().ToList();
    }
}

O(n · m) time — linear in total characters, no sorting. On paper, strictly better than the sorted-key approach for long strings.

In practice, the constant matters. A tuple of 26 integers takes more memory than a short sorted string ("aet" is 3 bytes; its tuple equivalent is 26 integers). Hashing a 26-element tuple involves more work than hashing a 3-character string, even though both are O(m) asymptotically. On LeetCode's test cases — mostly short strings — the sorted-key version usually runs faster because the keys are tiny.

I would reach for the frequency-tuple approach if the strings were long and the character alphabet were bounded. For this problem, both are correct and the difference is a timing artifact of the test suite. Know both; default to the one that is easier to read.

Complexity comparison

Space is O(n · m) for all three — you have to store all the strings somewhere.

Edge cases, each handled

Empty string [""]: The empty string sorts to "", which is a valid map key. It gets its own bucket and the output is [[""]]. No special-casing required in either approach.

All strings identical ["abc","abc","abc"]: All three produce key "abc" (already sorted) and land in one bucket. Output is [["abc","abc","abc"]]. The map has exactly one entry.

No anagrams at all ["a","b","c"]: Each string is its own key. The map grows to three entries and the output is [["a"],["b"],["c"]]. Neither approach has any issue here — they just produce many single-element buckets.

Single string ["a"]: One iteration, one bucket, output [["a"]]. The brute force also handles this without entering its inner loop.

All strings are anagrams ["abc","bca","cab"]: Every string produces key "abc". One bucket, one output group. This is the best case for the map: constant-size output regardless of input length.

Pattern recognition

Group Anagrams sits at the intersection of two recurring signals. First: "group elements that share some property" almost always means "derive a canonical key and use a hash map." The key is whatever you can compute from a single element that is identical for all elements in the same group.

Second: when the problem says "anagram," reach for either sort-to-canonical or character counting. Both reduce an ordering-dependent comparison to an ordering-independent signature.

Keywords that should trigger this pattern: "group," "cluster," "categorize," "same characters," "rearrange," "permutation of." If the output is a list of lists where each inner list contains "similar" items, you are almost certainly looking at a canonical-key bucketing problem.

The broader lesson: whenever you find yourself writing "for each element, scan all previously seen items to check similarity," stop. That nested scan is replaceable with a map from a derived key to a group.

Where this fits in the series

Contains Duplicate: seen set, membership only. Valid Anagram: frequency map, count equality. Group Anagrams: sorted key as bucket label, no element-to-element comparison at all. Each step reduces the comparisons per element — from O(n) scans down to O(1) map lookups — by choosing a smarter key.

The next natural extension is Top K Frequent Elements, where the key is not the element itself or its sorted form but its frequency. Same bucketing instinct, different key derivation.

Related problems

• 242. Valid Anagram — the direct predecessor. Single pair check rather than group-by. Understanding this first makes the key derivation here obvious.
• 438. Find All Anagrams in a String — frequency-array approach with a sliding window. The same 26-element count array, kept up to date as you slide.
• 567. Permutation in String — like 438 but returns a boolean. Slightly simpler window management.