Group Anagrams

1. Problem & Core Objective

The problem

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

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

Input:  strs = [""]        Output: [[""]]
Input:  strs = ["a"]       Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters

What the interviewer is actually testing

This is the first genuinely interesting question in the section, and the skill it tests is key design.

1. Can you invent a canonical form? You need a value that is identical for every member of a group and different across groups. Nothing in the problem hands you one — you have to construct it.
2. Do you avoid O(n²) pairwise comparison? The naive instinct is "compare every string to every other". Grouping by a computed key replaces that entirely.
3. Do you know that int[] can't be a HashMap key in Java? This is the question where that bites, and where the fix has to be explicit.
4. Can you weigh two valid keys? Sorted-string vs count-signature have different complexities, and the choice depends on word length.

The move being tested is: "stop comparing things, start labelling them."

2. First-Principles Thought Process

Step 1 — Constraints

• n up to 10^4 strings.
• k (each string's length) up to 100.

So total input is at most 10^6 characters.

• O(n²) pairwise comparisons → 10^8 comparisons, each costing up to O(k) → far too slow.
• O(n · k) → 10^6. Comfortable.
• O(n · k log k) → 10^6 × ~7 ≈ 7 × 10^6. Also fine.

Both key designs fit. The comparison between them is the discussion, not a pass/fail.

Step 2 — Name the brute force and its waste

for each string a:
    for each existing group g:
        if isAnagram(a, g.first()): add a to g

O(n²·k) in the worst case (all strings distinct). The waste: you're repeatedly comparing strings when you could be classifying them.

Step 3 — The reframe

Instead of asking "is a an anagram of b?" for every pair, ask once per string:

"What group does this string belong to?"

If you can compute a label for each string such that anagrams get identical labels, then grouping is just a HashMap<label, List<String>> and one pass.

This is the general move:

Pairwise comparison → compute a canonical key → group by it. O(n²) becomes O(n).

Step 4 — Design the canonical form

You need a function key(s) where key(a) == key(b) iff a and b are anagrams.

Recall from Valid Anagram: two strings are anagrams iff they have identical character counts. So the key must encode exactly "which characters, how many" while discarding order.

Two natural candidates:

(a) Sort the characters. "eat" → "aet", "tea" → "aet". Anagrams sort to the same string by definition. Cost: O(k log k) per string.

(b) The count signature. Build int[26] of character counts and serialize it. "eat" → [1,0,0,0,1,...,1,...]. Anagrams have identical counts by definition. Cost: O(k) per string — no log k factor.

Step 5 — The Java-specific obstacle

Option (b) produces an int[]. The obvious next step fails:

Map<int[], List<String>> groups = new HashMap<>();     // ✗ this does not work

Arrays in Java do not override equals or hashCode — they use reference identity. Two distinct int[] objects with identical contents are never equal as far as a HashMap is concerned. Every string would land in its own group.

The fix is to convert the counts to something with content-based equality — a String. See 05.

3. Solution Paths

Approach 1 — Brute force: compare against each group

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> groups = new ArrayList<>();

    for (String s : strs) {
        boolean placed = false;
        for (List<String> g : groups) {
            if (isAnagram(s, g.get(0))) { g.add(s); placed = true; break; }
        }
        if (!placed) {
            List<String> ng = new ArrayList<>();
            ng.add(s);
            groups.add(ng);
        }
    }
    return groups;
}

• Time: O(n² · k) worst case — every string compared against every existing group.
• Space: O(n · k) for the output.

Name it and reject it. Its only value is motivating the key idea.

Counter-questions on this approach

⭐ "That's O(n² · k). What's the structurally wasted work?"

I'm repeatedly comparing strings when I should be classifying them. Every comparison re-derives information I could have computed once. If I can compute a single label per string such that anagrams share it, grouping becomes one pass into a hash map.

"Why compare only against g.get(0) rather than every member of the group?"

Because anagram-ness is transitive — if the new string matches any one member, it matches all of them. Checking the first is sufficient. That's worth stating; it's a small correctness argument the code depends on.

Approach 2 — Sorted string as the key

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

    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);              // "eat" -> "aet"

        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

How it works. Each string is reduced to its sorted form. Anagrams collapse to the same sorted string, so they collide in the same map bucket by design.

Trace on ["eat","tea","tan","ate","nat","bat"]:

Result: [[eat,tea,ate], [tan,nat], [bat]] ✓

• Time: O(n · k log k) — sorting each of n strings of length k.
• Space: O(n · k) for the map and output.

This is a perfectly strong answer. It's concise, obviously correct, and the canonical-form idea is fully visible. Many interviewers accept it as final.

Counter-questions on this approach

⭐ "You're sorting each word, but you only need character counts. Why pay the log k?"

Legitimate — counting is O(k) versus O(k log k). With k capped at 100 the practical gap is modest, so I'd accept sorting for readability on short words and switch to counting if words could be long. The point is that it's a deliberate choice, not a default.

"Does this handle the empty string?"

Yes — it sorts to "", which becomes its own key and therefore its own group. [""] correctly returns [[""]].

Approach 3 — Count signature as the key (optimal)

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

    for (String s : strs) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

        String key = Arrays.toString(count);          // "[1, 0, 0, 0, 1, ...]"

        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

How it works. Identical to Approach 2 except the key is a letter-count signature rather than a sorted string. Since anagrams have identical counts, they produce identical signatures.

Arrays.toString(count) is not decoration — it's what makes the key work. Using the int[] directly would put every string in its own group, because arrays compare by identity.

Building the key more cheaply. Arrays.toString produces a ~100-character string with brackets and spaces. A tighter encoding:

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
    sb.append('#').append(count[i]);                  // "#1#0#0#0#1..."
}
String key = sb.toString();

The # delimiter is essential — without it, counts [1, 11] and [11, 1] would both serialize to "111". A separator makes the encoding unambiguous, the same principle as Encode and Decode Strings.

• Time: O(n · k) — counting is linear, building the 26-slot key is constant.
• Space: O(n · k).

Counter-questions on this approach

⭐ "Why can't you just use the int[] count array directly as the map key?"

Because arrays in Java don't override equals or hashCode — they inherit reference identity from Object. Two distinct int[] objects with identical contents are never equal to a HashMap, so every single string would hash to a different bucket and land in its own group. The array must be converted to something with content-based equality.

⭐ "Isn't Arrays.toString wasteful — roughly a 100-character string per word?"

Yes, and it's the price of getting content-based equality. A tighter encoding builds the key with a StringBuilder and # separators, dropping the brackets and spaces. List<Integer> also works and skips the string entirely, at the cost of boxing.

"Why does the delimited version need the # at all?"

Without a separator the encoding is ambiguous: counts [1, 11, …] and [11, 1, …] both serialize to "111…" and would silently merge two different groups. The delimiter makes the encoding injective — the same principle as length-prefixing in Encode and Decode Strings.

"This relies on the alphabet being exactly a–z. What if it isn't?"

c - 'a' breaks immediately. I'd fall back to a HashMap<Character,Integer> for the counts and build the key from its sorted entries — a map has no inherent order, so I'd have to impose one for the key to be canonical. Or just use the sorted-string key, which handles any alphabet with no changes.

Approach 4 — Prime-product key (know it, don't use it)

Assign each letter a distinct prime and multiply. Anagrams produce the same product, by unique factorization.

int[] PRIMES = {2, 3, 5, 7, 11, ...};                 // 26 primes
long key = 1;
for (char c : s.toCharArray()) key *= PRIMES[c - 'a'];

Elegant and wrong at scale. With k up to 100, the product overflows long almost immediately — 100 letters of 'z' (101) would be 101^100, astronomically beyond 64 bits. Overflow silently creates false groupings.

Mention it as a known idea and reject it on overflow grounds. Knowing why it fails is the valuable part.

Counter-questions on this approach

⭐ "This is mathematically elegant — unique factorization guarantees correctness. Why reject it?"

The maths is sound; the arithmetic isn't. With k up to 100, a word of 100 zs gives 101^100, which is astronomically beyond 64 bits. The product overflows silently and wraps, so two non-anagrams can collide and be merged into the same group. It fails quietly, which is the worst failure mode. It would be viable only with BigInteger, at which point it's slower than counting.

Comparison

4. Why the Optimal Wins

Against brute force. Comparing every pair is O(n²). Computing a label per string is O(n). The map's O(1) lookup does the matching that the nested loop was doing by hand. This is the single most reusable idea in the section:

When a problem asks you to group things by an equivalence relation, don't compare — compute a canonical representative and hash it.

Against the sorted key. Both are correct; the count signature removes the log k factor.

The honest framing:

"Sorting is O(k log k) per string, counting is O(k). With k up to 100 that's a factor of roughly 7 — real but not dramatic. If words could be much longer, the gap widens. I'll use counting since it's asymptotically better, though I'd accept sorting for readability if the words are short."

That trade-off statement is worth more than the code. It shows you chose rather than recited.

Why O(n · k) is the floor. You must read every character of every string — an adversary can change any unread character and alter the grouping. Total input is n · k characters, so O(n · k) is optimal.

5. Java Prerequisites

Sorting a string's characters

char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);

Strings are immutable, so there's no in-place sort. You must convert to char[], sort that, then build a new String. new String(char[]) copies the array.

computeIfAbsent — the grouping idiom

groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);

Reads as: "get the list for this key; if there isn't one, create an empty list and store it. Either way, hand the list back so I can add to it."

It replaces:

if (!groups.containsKey(key)) groups.put(key, new ArrayList<>());
groups.get(key).add(s);

It returns the value, which is what allows chaining .add(s) directly. See 02 §1.3.

int[] cannot be a HashMap key

Map<int[], String> m = new HashMap<>();
m.put(new int[]{1,2}, "v");
m.get(new int[]{1,2});          // null — different object, arrays use identity

The three standard fixes:

See 05.

Returning the result

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

groups.values() is a view of the map, typed Collection<List<String>>. The method signature demands List<List<String>>, so wrap it in an ArrayList — which also detaches it from the map.

Character-to-index arithmetic

count[c - 'a']++;        // 'a'->0, 'b'->1, ... 'z'->25

Only valid for lowercase a–z. For mixed case or Unicode, use a HashMap<Character,Integer>.

6. Interview Communication Guide

Clarifying questions

1. "Are the strings lowercase English only?" — decides whether int[26] is available.
2. "How long can the strings be?" — drives the sorted-key vs count-key choice.
3. "Does the output order matter — of groups, or within groups?" — the problem says no; confirming saves you from sorting unnecessarily.
4. "Can strings be empty?" — [""] should return [[""]], and the empty string is its own valid group.
5. "Can the same string appear twice?" — duplicates go in the same group; nothing special needed.

The pitch

"The brute force compares each string against every existing group — O(n²·k).

Instead of comparing, I'll label. If I can compute a key that's identical for anagrams and different otherwise, grouping becomes one pass into a HashMap<key, List<String>>.

Two natural keys. Sorting each string gives a canonical form — "eat" and "tea" both become "aet" — at O(k log k) per string. Or, since the alphabet is lowercase-only, I can count letters into an int[26] and use that signature, at O(k).

I'll use the count signature since it drops the log k. One Java detail: I can't use the int[] directly as a map key — arrays don't override equals/hashCode, so every string would land in its own group. I'll serialize it to a string with separators.

O(n·k) time and space."

Edge cases to raise proactively

The # separator is the detail to volunteer. Without it, counts [1, 11, ...] and [11, 1, ...] both serialize to "111..." and collide. Raising that unprompted shows you thought about the encoding rather than reaching for Arrays.toString by habit.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if the strings are Unicode?"

int[26] breaks. Use HashMap<Character,Integer> for counts, then build the key from its sorted entries — a map has no order, so you must impose one for the key to be canonical. Or just fall back to sorting the string, which handles any alphabet.

Also note Java char is 16 bits, so characters outside the Basic Multilingual Plane occupy two chars. Use s.codePoints() to iterate correctly.

"What if the input doesn't fit in memory?"

The key function is deterministic, so this shards cleanly: hash each string's key to pick a machine, send it there, and each machine groups independently. It's the map step of MapReduce, and the canonical key is exactly the reduce key.

"Can you avoid storing all the strings?"

Only if the output permits it. If you need counts per group rather than the strings, store Map<key, Integer> — O(n) keys instead of O(n·k) characters.

"Group by something other than anagrams — same digit set, same word length?"

Only key() changes; the surrounding code is identical. That's the strength of the pattern: the grouping machinery is independent of the equivalence relation.

"What if you had to detect anagram pairs on a stream?"

Keep the HashMap<key, List<String>> alive and query it as each string arrives — O(k) per string. Nothing about the structure needs to change, which is a good sign the design is right.