DSA-004 · Canonical signatures and grouped multiplicity

Group Anagrams

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3005 deterministic checks. Learner drafts are not executed.

Understand the problem

Partition a list of lowercase words into groups of anagrams. Keep every occurrence, including repeated equal words, and retain input order within each group.

words is a non-null String[] with 0–10,000 non-null lowercase a–z strings, each length 0–100. Total character count is at most 100,000.
Every input occurrence appears in exactly one nonempty output group. Outer group order is unrestricted; each group preserves the input-relative order of its words.
Preserve the input array. Returned groups are independent mutable lists. Strings themselves are immutable and may be referenced directly. Empty input returns no groups; empty words belong together.

Examples

Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Members share frequency vectors; another outer group order is equally valid.
Input: ["","a","","a"]
Output: [["",""],["a","a"]]
Empty words and duplicate occurrences must not disappear.

Before you start

Anagram frequency vectors
Hash-map key equality and independent mutable output groups

Recognize the structure

Use a canonical signature whose equality is exactly anagram equivalence. This is grouping by an invariant, not pairwise comparison against every group member. Key design is part of correctness, not merely an implementation detail.

Try before revealing

Hint 1

What canonical representation identifies the same letter multiset?

Hint 2

Map that signature to a list of original occurrences.

Hint 3

Use an unambiguous 26-count key and append words in input order.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Sort each word to form a key

For each word, sort a char-array copy and use the resulting String as its key. "tea", "eat", and "ate" all map to "aet". Append the original word to that key’s list. This is a correct expected-hashing baseline; sorting each length-L word costs O(L log L), plus key storage and the output references.

Improve the baseline

Count instead of sorting

Build a 26-slot letter-frequency array for each word. Fixed alphabet size permits linear scanning of its characters.

Encode the complete vector unambiguously

Arrays.toString(counts) includes positions and delimiters. It distinguishes counts such as [1,11] from [11,1], unlike naive concatenation. A raw int[] is not a value-equality map key in Java.

Append occurrences to one owned group

Use computeIfAbsent to create one list per signature, then append every input word in order. LinkedHashMap gives reproducible first-seen group order in this reference, although the public contract permits other outer orders.

Why it is correct

Signature equivalence

Two lowercase words are anagrams exactly when all 26 counts agree. The delimited encoding represents that complete vector without ambiguity.

Processed-prefix invariant

After each word, each signature group contains precisely the processed occurrences with that signature, in input order. Appending once to the matching group preserves coverage, multiplicity, and order.

Final partition

Every occurrence is processed exactly once, and no group combines unequal signatures. The final groups are therefore disjoint by occurrence and exhaustive; map/group loops are finite.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public final class Solution {
    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new LinkedHashMap<>();
        for (String word : words) {
            int[] counts = new int[26];
            for (int i = 0; i < word.length(); i++) counts[word.charAt(i) - 'a']++;
            String key = Arrays.toString(counts);
            groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
    public static List<List<String>> baseline(String[] words) {
        Map<String, List<String>> groups = new LinkedHashMap<>();
        for (String word : words) {
            char[] sorted = word.toCharArray(); Arrays.sort(sorted);
            String key = new String(sorted);
            groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
}

Read the meaningful blocks

Do not use an array directly as a key

Java arrays use identity equality by default; equal count contents in different arrays would not group together.

Create lists lazily per signature

A shared list reused for several keys would alias groups and mix nonanagrams.

Keep original strings in the output

The key is only a classifier. Return the original word occurrences, not sorted replacements.

Complexity

With n words, total T characters, fixed alphabet 26, and g groups, expected time is O(T+26n). Key creation/hashing is O(26) per word under the stated length bounds, not content-free O(1) for arbitrary signatures.

The result stores O(n+g) list/reference structure; the map retains O(26g) signature characters under bounded counts, plus O(26) temporary counts. Sorted-key baseline adds Σ O(L log L) sorting work and retains sorted keys of total length up to T. Neither method mutates input.

Exact-state walkthroughs

Reveal normal and boundary traces

Shared signatures and duplicate occurrences

Input: ["eat","tea","tan","ate","eat"] · Result: [["eat","tea","ate","eat"],["tan"]]

Step 1 of 12: No occurrences have been grouped yet.

Each group owns one complete frequency signature.

Owned groups of original word occurrences

Empty at this step.

State after this step
Variable	Value
groups	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.LinkedHashMap;
 4 import java.util.List;
 5 import java.util.Map;
 6 public final class Solution {
 7     public static List<List<String>> groupAnagrams(String[] words) {
 8         Map<String, List<String>> groups = new LinkedHashMap<>();
 9         for (String word : words) {
10             int[] counts = new int[26];
11             for (int i = 0; i < word.length(); i++) counts[word.charAt(i) - 'a']++;
12             String key = Arrays.toString(counts);
13             groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
14         }
15         return new ArrayList<>(groups.values());
16     }
17     public static List<List<String>> baseline(String[] words) {
18         Map<String, List<String>> groups = new LinkedHashMap<>();
19         for (String word : words) {
20             char[] sorted = word.toCharArray(); Arrays.sort(sorted);
21             String key = new String(sorted);
22             groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
23         }
24         return new ArrayList<>(groups.values());
25     }
26 }
27

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

No occurrences have been grouped yet.
Each group owns one complete frequency signature.
groups
[]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
0
word
"eat"
counts
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
0
word
"eat"
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat"]]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
1
word
"tea"
counts
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat"]]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
1
word
"tea"
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea"]]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
2
word
"tan"
counts
[1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0]
key
"[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea"]]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
2
word
"tan"
key
"[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea"],["tan"]]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
3
word
"ate"
counts
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea"],["tan"]]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
3
word
"ate"
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea","ate"],["tan"]]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
4
word
"eat"
counts
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea","ate"],["tan"]]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
4
word
"eat"
key
"[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
groups
[["eat","tea","ate","eat"],["tan"]]
Return the contract result.
The completed state satisfies the declared output and mutation contract.
result
[["eat","tea","ate","eat"],["tan"]]

Empty words share a signature

Input: ["","a",""] · Result: [["",""],["a"]]

Step 1 of 8: No occurrences have been grouped yet.

Each group owns one complete frequency signature.

Owned groups of original word occurrences

Empty at this step.

State after this step
Variable	Value
groups	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.LinkedHashMap;
 4 import java.util.List;
 5 import java.util.Map;
 6 public final class Solution {
 7     public static List<List<String>> groupAnagrams(String[] words) {
 8         Map<String, List<String>> groups = new LinkedHashMap<>();
 9         for (String word : words) {
10             int[] counts = new int[26];
11             for (int i = 0; i < word.length(); i++) counts[word.charAt(i) - 'a']++;
12             String key = Arrays.toString(counts);
13             groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
14         }
15         return new ArrayList<>(groups.values());
16     }
17     public static List<List<String>> baseline(String[] words) {
18         Map<String, List<String>> groups = new LinkedHashMap<>();
19         for (String word : words) {
20             char[] sorted = word.toCharArray(); Arrays.sort(sorted);
21             String key = new String(sorted);
22             groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
23         }
24         return new ArrayList<>(groups.values());
25     }
26 }
27

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

No occurrences have been grouped yet.
Each group owns one complete frequency signature.
groups
[]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
0
word
""
counts
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
key
"[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
groups
[]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
0
word
""
key
"[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
groups
[[""]]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
1
word
"a"
counts
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
key
"[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
groups
[[""]]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
1
word
"a"
key
"[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
groups
[[""],["a"]]
Count this word and encode all 26 positions.
Equal keys mean equal letter multiplicities; separators make the encoding unambiguous.
index
2
word
""
counts
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
key
"[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
groups
[[""],["a"]]
Append this occurrence to its owned group.
Every processed occurrence appears once, in input-relative order inside its group.
index
2
word
""
key
"[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
groups
[["",""],["a"]]
Return the contract result.
The completed state satisfies the declared output and mutation contract.
result
[["",""],["a"]]

Test the contract

Input: []
Output: []
No groups.
Input: [""]
Output: [[""]]
One empty word.
Input: ["ab","ba","ab"]
Output: [["ab","ba","ab"]]
Multiplicity and within-group order.
Input: ["a","b"]
Output: [["a"],["b"]]
Different signatures.

Common mistakes and counterexamples

Use a set of words

Counterexample: ["a","a"] must retain two occurrences.

Append every occurrence to its group.

Use raw int[] keys

Counterexample: New arrays for "ab" and "ba" compare by identity.

Use a value-equality key or an unambiguous encoding.

Concatenate counts without boundaries

Counterexample: [1,11] and [11,1] both look like "111".

Retain separators and fixed positions.

Compare one arbitrary outer order

Counterexample: Different map iteration orders can still produce a valid partition.

Compare group content and multiplicity semantically.

Follow-ups

Allow arbitrary Unicode.

Define code-point and normalization semantics, then build a sorted sparse count representation or another value-equality signature. Its size and sort/hash costs depend on the actual alphabet.

Return only groups with at least two occurrences.

Build complete groups, then filter by list size. Decide whether identical repeated words qualify; this contract counts occurrences, not distinct spellings.

Process a stream too large to retain.

A complete materialized grouping requires output storage. Consider partitioning by signature to external storage, with a clear policy for emission and ordering rather than claiming bounded memory for all groups.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 152/20,000 characters

Self-review

My key equality matches anagram equivalence.I preserve occurrences and within-group order.I compare valid partitions rather than one map iteration order.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Hashing foundations: identity, frequency, and boundaries

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These are standard algorithmic tasks; no company-frequency or interview-outcome claims are made.