LeetCode 49 – Group Anagrams

Group Anagrams is a hashing problem wearing a string problem's clothes. Once you see it as "group these by a computed key", the only question left is what the key should be — and that choice is the entire difference between a good answer and a mediocre one.

The problem

Given an array of strings, group the anagrams together. Return the groups in any order, and the strings within a group in any order.

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

[""]      -> [[""]]
["a"]     -> [["a"]]

Find the invariant

Do not compare strings to each other — that is O(n²) comparisons before you have even checked one pair. Instead find something that is identical for anagrams and different for everything else, and use it as a hash key. One pass, and the grouping falls out.

Two candidates, and they are not equally good.

Sort each word. "eat", "tea" and "ate" all become "aet". Correct, two lines, and it costs O(k log k) per word.

Count each word's letters. Anagrams are by definition the same multiset of letters, so a 26-slot frequency vector is the invariant, and building it is O(k) — no comparison sort needed, because the alphabet is small and fixed.

Counting is asymptotically better. Say the sorted-key version first because it is obvious and correct, then improve it — that progression is what is being watched.

The separator that everyone forgets

Turning the count vector into a string key has a trap that only shows up on words long enough to push a count into double digits.

counts [1, 11, 0, ...]  naively -> "1110..."
counts [11, 1, 0, ...]  naively -> "1110..."      same key, different words!

A word with one a and eleven bs produces the same concatenation as one with eleven as and one b. They are not anagrams and they would be grouped together. Put a delimiter between the counts — "#1#11#0…" — and the ambiguity is gone.

Test inputs are usually too short to expose this, which is exactly why it is worth mentioning unprompted. In Python the problem does not arise at all, because a tuple of ints is hashable directly and never gets flattened into text.

Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String s : strs) {
            groups.computeIfAbsent(key(s), k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(groups.values());
    }

    /** Anagrams have identical letter counts, so the count vector is the invariant. */
    private String key(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        for (int count : counts) {
            sb.append('#').append(count);   // separator: 1,11 must not collide with 11,1
        }
        return sb.toString();
    }
}

computeIfAbsent replaces the containsKey / get / put dance and hashes once instead of three times.

counts[c - 'a'] assumes lowercase ASCII, which this problem guarantees. Say that you are relying on it — if the interviewer adds Unicode or mixed case, the fix is a Map<Character, Integer> or a normalisation pass, and noticing the assumption is better than being caught by it.

Python

from collections import defaultdict


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:
                counts[ord(c) - ord("a")] += 1

            groups[tuple(counts)].append(s)     # a tuple is hashable; no separator needed

        return list(groups.values())

The tuple key is the neat part: it has structure, so (1, 11) and (11, 1) are simply different keys and the delimiter problem never exists. A list would not work — it is unhashable, which is Python telling you a mutable object cannot be a dictionary key.

Complexity

n strings of length up to k. Counting builds each key in a single pass over the word; sorting pays an extra log k. Space is the output plus the keys, and neither approach avoids storing the strings.

In practice the sorted key often wins on short words — 26 slots is a lot of overhead for a three-letter string, and Arrays.sort on a tiny array is very fast. Saying that shows you can tell an asymptotic argument from a real one.

The pattern

"Group by a computed invariant" recurs constantly once you spot it: Valid Anagram (242) is this key comparison for exactly two strings; Find All Anagrams in a String (438) slides a count window across a string; Group Shifted Strings (249) is the same shape with a different invariant — the sequence of gaps between letters, so "abc" and "bcd" group together.

The general move is: what stays the same across everything I want grouped? Compute that, hash it, done.

What the interviewer is checking

• That you group by a key rather than comparing strings pairwise.
• That you offer the sorted key and then improve it to counting.
• The delimiter — or a tuple key — so double-digit counts cannot collide.
• That you state the lowercase-ASCII assumption rather than absorbing it silently.
• Empty string and single-character inputs, which must still form groups.
• That you use computeIfAbsent / defaultdict rather than a check-then-insert.