A catalog ingest job is given product titles, SKU tokens, and the log fragments ops pasted beside them. Merchandising wants one bucket per jumble: eat, tea, and ate are the same listing spelled three ways; bat is not. The first version treated each title as a Valid Anagram scan against every remaining ungrouped string. A few dozen SKUs in staging grouped before coffee. A few hundred thousand catalog titles were still pairwise-checking when the nightly window closed.

Group Anagrams asks you to bucket strings that share the same letters. Valid Anagram is that frequency test on one pair. Pairwise checks use it and still pay quadratic in n.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about hashing a signature so every anagram of a word lands in one list, not restarting a Valid-Anagram scan for every pair.

The problem

Given a String[] strs, group the strings that are anagrams of each other. Order of groups, and order of strings inside a group, do not matter.

strs = ["eat","tea","tan","ate","nat","bat"]  →  [["eat","tea","ate"], ["tan","nat"], ["bat"]]
strs = [""]                                    →  [[""]]
strs = ["a"]                                   →  [["a"]]

Note: [""] is a group of one empty string, not an empty result. Identical copies of the same word belong in the same bucket. Find All Anagrams in a String is a different job: a sliding window over one haystack, not grouping a list.

Pairwise anagram checks are the honest brute force

For each unused string, scan the rest with a Valid-Anagram check (sort both, or count 26 letters) and mark matches used. Correct. Quadratic in n times the anagram cost.

List<List<String>> groupAnagramsNested(String[] strs) {
    int n = strs.length;
    boolean[] used = new boolean[n];
    List<List<String>> groups = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (used[i]) {
            continue;
        }
        List<String> group = new ArrayList<>();
        group.add(strs[i]);
        used[i] = true;
        for (int j = i + 1; j < n; j++) {
            if (!used[j] && isAnagram(strs[i], strs[j])) {
                group.add(strs[j]);
                used[j] = true;
            }
        }
        groups.add(group);
    }
    return groups;
}

boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }
    char[] ca = a.toCharArray();
    char[] cb = b.toCharArray();
    Arrays.sort(ca);
    Arrays.sort(cb);
    return Arrays.equals(ca, cb);
}

At n = 20 this is a rounding error. At production size you paid a nested Valid-Anagram for a question one map answers in a pass: same signature, same bucket.

One pass: map the signature to a list

Walk left to right. The map key is not the word — it is a signature every anagram shares:

  • Sorted letters as a String: eat, tea, ate all become "aet".
  • Or a 26-count key: stringify the frequencies with a delimiter so 11 and 1,1 cannot collide.

On each string, compute the key, open a list if the key is new, append the original. Return the map’s values. You never restart a pairwise scan.

strs = [eat, tea, tan, ate, nat, bat]

eat  key=aet   map {aet:[eat]}
tea  key=aet   map {aet:[eat, tea]}
tan  key=ant   map {aet:[eat, tea], ant:[tan]}
ate  key=aet   map {aet:[eat, tea, ate], ant:[tan]}
nat  key=ant   map {aet:[eat, tea, ate], ant:[tan, nat]}
bat  key=abt   map {aet:[eat, tea, ate], ant:[tan, nat], abt:[bat]}

The Java is that walk with the sorted-letter key:

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> buckets = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(buckets.values());
}

Time is expected O(n k log k) with a sorted key — one pass, one sort of length k per string (n strings, longest length k). A 26-count key drops the log and is expected O(n k). Space is O(n k) to hold the originals plus their keys. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Do not put an int[] count in the map as the key. Array equals is identity. Two identical frequency arrays are different objects. Stringify the counts with a delimiter, or sort the letters into a String. Store the original word in the list, not the key.

What interviewers usually poke next

  • Count key vs sorted key. Twenty-six counters and a delimited string is O(n k) and assumes lowercase a–z. Sorted letters work for any comparable characters and cost the extra log k.
  • Unicode / mixed case. The 26-slot array is then the wrong alphabet. Ask the range; keep the sorted-letter key, or count in a map of code points.
  • Find all anagrams in one string. That is Find All Anagrams in a String: a sliding window over a haystack, not grouping a list of words.
  • Return indices, not copies. Production may bucket indexes into strs instead of storing every original again. The signature is unchanged.

You are done with this problem when you can say, out loud, why pairwise Valid Anagram is correct, why the map key is a signature and not the word, and why an int[] is not a HashMap key.