DSA-004 · FOCUSED PRACTICE
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.
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.
No unsaved text changes · 152/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
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.
Empty at 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.
Empty at 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.