Loading…

mediumStringsLC #49Frequently asked

Group Anagrams

Q: How do you solve Group Anagrams using the Sorted-Word Key approach?

When to use it: The cleanest first answer — easy to reason about and to code. For every word, compute its sorted character string and use that as a map key. All anagrams of a word sort to the identical string, so they land in the same bucket. After processing every word, the map's values are exactly the groups. **Why the sorted form is a valid key.** Sorting is a canonicalization: it maps all permutations of the same multiset of letters to one representative. Two words share a sorted form iff they're anagrams — which is precisely the grouping rule. Time complexity: O(n·k log k). Space complexity: O(n·k).

Q: How do you solve Group Anagrams using the Character-Count Key (Optimal) approach?

When to use it: The improvement: replace per-word sorting with O(k) counting. Instead of sorting, count each word's 26 letter frequencies and use that frequency signature as the map key. Anagrams have identical signatures, so they bucket together — and we avoid the log factor sorting incurred. **Encoding the key.** The count array itself isn't directly hashable as a map key in Java, so encode it as a string like `"1#0#0#...#2"` (counts separated by a delimiter to avoid ambiguity, e.g. 1,12 vs 11,2). In Python a `tuple(count)` is hashable and clean. Either way, equal signatures ⇒ same bucket. Time complexity: O(n·k). Space complexity: O(n·k).

LCPractice

Arrays & Hashing · 4 of 83 · 7 min

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An anagram is a word formed by rearranging the letters of another, using all the original letters exactly once.

In plain English

Cluster the input words so that each cluster contains exactly the words that are rearrangements of one another. We need a way to recognize 'same letters' that's identical for every member of a group.

Examples

Example 1

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Note: eat/tea/ate share key 'aet'; tan/nat share 'ant'; bat is alone.

Example 2

Input: strs = [""]
Output: [[""]]
Note: A single empty string forms one group.

Example 3

Input: strs = ["a"]
Output: [["a"]]
Note: A single character is its own group.

Constraints

1 ≤ strs.length ≤ 10⁴
0 ≤ strs[i].length ≤ 100
strs[i] consists of lowercase English letters

Clarifying questions4First question: Does the order of groups, or words within a group, matter?Explore questions

Q1.Does the order of groups, or words within a group, matter?
No — any order is accepted, which is why a hash map (unordered) is fine.
Q2.Are the strings lowercase English only?
Yes per constraints, so a 26-slot count key is valid. For Unicode you'd key by a map/encoded counts.
Q3.Can a word be empty?
Yes — empty strings are anagrams of each other and form their own group under either key.
Q4.How long can the words get?
Up to 100 chars. That makes the O(k) count key meaningfully cheaper than the O(k log k) sort key at scale.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Group words that are anagrams of each other. The trick is a canonical key shared by all anagrams of a word — either the sorted word or a 26-length character-count signature. Bucket every word into a hash map keyed by that signature, then return the buckets. Sorted key: O(n·k log k); count key: O(n·k), where n = number of words, k = max word length.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you invent a canonical key that all anagrams share and use it as a hash-map bucket key — and whether you can improve the key from O(k log k) sorting to O(k) counting.

Where candidates slip

Comparing every pair of words for anagram-ness (O(n²·k)), or building a key that isn't actually shared by all anagrams.

How to stand out

Offer both keys, explain the count-signature beats sorting for long words, and note the map values are the original words so no information is lost.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sorted-Word Key	`O(n·k log k)`	`O(n·k)`	The cleanest first answer — easy to reason about and to code.	Read
2	Character-Count Key (Optimal)Optimal	`O(n·k)`	`O(n·k)`	The improvement: replace per-word sorting with O(k) counting.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewGroup anagramsChoose a canonical keysort the wordcount lettersExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sorted-Word Key

TimeO(n·k log k)SpaceO(n·k)

The cleanest first answer — easy to reason about and to code.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What single value is identical for every anagram of a word, regardless of letter order?

2Hint 2Explore hint

Sorting a word gives a canonical form: 'eat', 'tea', 'ate' all sort to 'aet'.

3Hint 3Explore hint

Use that sorted form as a hash-map key; append each original word to its bucket.

A · Core idea

For every word, compute its sorted character string and use that as a map key. All anagrams of a word sort to the identical string, so they land in the same bucket. After processing every word, the map's values are exactly the groups.

Why the sorted form is a valid key. Sorting is a canonicalization: it maps all permutations of the same multiset of letters to one representative. Two words share a sorted form iff they're anagrams — which is precisely the grouping rule.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

strs = ["eat","tea","tan","bat"]

eat

sorted → 'aet'

State{aet:[eat]}

Final result[[eat,tea],[tan],[bat]]

C · Code with teaching comments

Reference implementation previewpublic List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> groups = new HashMap<>(); for (String word : strs) { char[] chars = word.toCharArray(); Arrays.sort(chars);Explore the full code

solution.javaJava

Sorted-Word Key — reference

2 teaching notes

1
public List<List<String>> groupAnagrams(String[] strs) {
2
    Map<String, List<String>> groups = new HashMap<>();
3
    for (String word : strs) {
4
        char[] chars = word.toCharArray();
5
        // Canonicalize the word — anagrams now share an identical char array.
6
        Arrays.sort(chars);
7
        String key = new String(chars);
8
        // Create the bucket if missing, then append the ORIGINAL word.
9
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
10
    }
11
    return new ArrayList<>(groups.values());
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n·k log k) timeO(n·k) spaceOpen the invariant and proofExplore the proof

This reuses the 'canonicalize then compare' idea from Valid Anagram, but instead of comparing two forms we index by the form. The map turns an O(n²) all-pairs comparison into O(n) bucket insertions.

ComplexityO(n·k log k) time, O(n·k) space — For each of n words we sort k characters (O(k log k)) and do O(1) map work. Total O(n·k log k). We store every word once → O(n·k) space.

E · Edge cases and pitfalls2Storing the sorted key instead of the original word in the bucket.Explore edge cases

Pitfalls

Storing the sorted key instead of the original word in the bucket.
Forgetting computeIfAbsent / defaultdict and NPE-ing on a missing key.

03.2

Approach 2 of 2 · Optimal

Character-Count Key (Optimal)

TimeO(n·k)SpaceO(n·k)

The improvement: replace per-word sorting with O(k) counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Sorting each word costs O(k log k). Can you build a canonical key in O(k)?

2Hint 2Explore hint

Two words are anagrams iff their 26-letter counts match. Use those counts as the key.

3Hint 3Explore hint

Encode the count vector into something hashable — a tuple in Python, a delimited string in Java.

A · Core idea

Instead of sorting, count each word's 26 letter frequencies and use that frequency signature as the map key. Anagrams have identical signatures, so they bucket together — and we avoid the log factor sorting incurred.

Encoding the key. The count array itself isn't directly hashable as a map key in Java, so encode it as a string like "1#0#0#...#2" (counts separated by a delimiter to avoid ambiguity, e.g. 1,12 vs 11,2). In Python a tuple(count) is hashable and clean. Either way, equal signatures ⇒ same bucket.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

strs = ["eat","tea","tan"]

Hash-map state

eat

ValueIndex / state

sig(eat)→ [eat]

Continue scanning

new bucket aet-sig

Final result[[eat,tea],[tan]]

C · Code with teaching comments

solution.javaJava

Character-Count Key (Optimal) — optimal

3 teaching notes

1
public List<List<String>> groupAnagrams(String[] strs) {
2
    Map<String, List<String>> groups = new HashMap<>();
3
    for (String word : strs) {
4
        int[] count = new int[26];
5
        for (char c : word.toCharArray()) {
6
            // Build the 26-letter histogram for this word in O(k).
7
            count[c - 'a']++;
8
        }
9
        StringBuilder key = new StringBuilder();
10
        for (int n : count) {
11
            // Delimiter prevents collisions like [1,12] vs [11,2].
12
            key.append(n).append('#');
13
        }
14
        // Bucket by the encoded signature; store the original word.
15
        groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(word);
16
    }
17
    return new ArrayList<>(groups.values());
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n·k) timeO(n·k) spaceOpen the invariant and proofExplore the proof

The count signature is the histogram from Valid Anagram, reused as a dictionary key. Trading the sort for a linear count is the canonical micro-optimization interviewers look for once you've shown the sort solution.

ComplexityO(n·k) time, O(n·k) space — Each word is scanned once to build a 26-length count (O(k)), and the encoded key is O(26)=O(k) to form/hash. Total O(n·k). Space O(n·k) to store the words.

E · Edge cases and pitfalls5strs = [""] — Empty word → all-zero count signature → its own single-element group.Explore edge cases

Edge cases handled

strs = [""]Empty word → all-zero count signature → its own single-element group.
strs = ["a","a"]Identical words share a signature → one group ["a","a"].

Pitfalls

Encoding counts without a delimiter — [1,12] and [11,2] can collide into the same string.
Using the raw int[] as a Java map key — arrays use identity equality, so every word becomes its own bucket.
Recomputing the key when retrieving — compute once per word and reuse.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> groups = new HashMap<>(); for (String word : strs) { int[] count = new int[26]; for (char c : word.toCharArray()) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

int[] as a HashMap key in Java

Arrays hash by identity, not contents, so two equal count vectors are treated as different keys and nothing groups. Encode the counts as a String (or use Arrays-based wrappers).

Explore the code comparison

Don't write this

Map<int[], List<String>> groups = new HashMap<>();
groups.computeIfAbsent(count, k -> new ArrayList<>()).add(word);

Write this instead

String key = encode(count); // e.g. join with '#'
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);

Ambiguous count encoding

Concatenating counts without separators makes [1,12] and [11,2] both become "112", merging unrelated groups. Use a delimiter.

Explore the code comparison

Don't write this

for (int n : count) key.append(n); // "112" is ambiguous

Write this instead

for (int n : count) key.append(n).append('#');

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Canonical key + hash-map bucketing

Code pattern to memorize

groups = defaultdict(list)
for word in strs:
    key = canonical(word)   # sorted(word) OR 26-count tuple
    groups[key].append(word)
return list(groups.values())

Rules to remember

1All anagrams must collapse to the same key — sort the word, or use a tuple of 26 counts.
2The count-tuple key is O(k) per word vs O(k log k) for sorting — faster for long words.
3Use the key only to bucket; the stored values are the original words, untouched.
4Pick a key type your map can hash: a string in Java (new String(count)), a tuple in Python.
5Return map.values() — order of groups doesn't matter per the problem.

Use this pattern when

Group / cluster items that share an equivalence (anagram, same digits, same shape)
'Partition this list by some normalized form'
Any time a canonical representative collapses many inputs to one bucket

Choose another pattern when

Just compare two strings → Valid Anagram (no bucketing needed)
Need anagram substrings of a text → sliding-window frequency
Equivalence can't be reduced to a hashable key → may need union-find

Interview takeaway

Bucketing by a canonical key is the go-to for any 'group things that are equivalent' problem. Choosing a cheap, collision-free key (sorted form or count signature) is the whole game.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical-key bucketing in a hash map. Reach for it on any 'group items that are equivalent under some normalization' problem. The count-signature key is the same histogram used by Valid Anagram and the sliding-window anagram problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
The two-word version — compare a single pair instead of bucketing many.
Find All Anagrams in a String
Coming soon
Slide a fixed-size window and compare frequency tables.
Group Shifted Strings
Coming soon
Same bucketing pattern with a shift-difference canonical key.

Same pattern

←

Contains Duplicate

Continue · Next problem

Product of Array Except Self

mediumStringsLC #49Frequently asked

Group Anagrams

LCPractice

Arrays & Hashing · 4 of 83 · 7 min

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An anagram is a word formed by rearranging the letters of another, using all the original letters exactly once.

In plain English

Cluster the input words so that each cluster contains exactly the words that are rearrangements of one another. We need a way to recognize 'same letters' that's identical for every member of a group.

Examples

Example 1

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Note: eat/tea/ate share key 'aet'; tan/nat share 'ant'; bat is alone.

Example 2

Input: strs = [""]
Output: [[""]]
Note: A single empty string forms one group.

Example 3

Input: strs = ["a"]
Output: [["a"]]
Note: A single character is its own group.

Constraints

1 ≤ strs.length ≤ 10⁴
0 ≤ strs[i].length ≤ 100
strs[i] consists of lowercase English letters

Clarifying questions4First question: Does the order of groups, or words within a group, matter?Explore questions

Q1.Does the order of groups, or words within a group, matter?
No — any order is accepted, which is why a hash map (unordered) is fine.
Q2.Are the strings lowercase English only?
Yes per constraints, so a 26-slot count key is valid. For Unicode you'd key by a map/encoded counts.
Q3.Can a word be empty?
Yes — empty strings are anagrams of each other and form their own group under either key.
Q4.How long can the words get?
Up to 100 chars. That makes the O(k) count key meaningfully cheaper than the O(k log k) sort key at scale.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you invent a canonical key that all anagrams share and use it as a hash-map bucket key — and whether you can improve the key from O(k log k) sorting to O(k) counting.

Where candidates slip

Comparing every pair of words for anagram-ness (O(n²·k)), or building a key that isn't actually shared by all anagrams.

How to stand out

Offer both keys, explain the count-signature beats sorting for long words, and note the map values are the original words so no information is lost.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sorted-Word Key	`O(n·k log k)`	`O(n·k)`	The cleanest first answer — easy to reason about and to code.	Read
2	Character-Count Key (Optimal)Optimal	`O(n·k)`	`O(n·k)`	The improvement: replace per-word sorting with O(k) counting.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sorted-Word Key

TimeO(n·k log k)SpaceO(n·k)

The cleanest first answer — easy to reason about and to code.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What single value is identical for every anagram of a word, regardless of letter order?

2Hint 2Explore hint

Sorting a word gives a canonical form: 'eat', 'tea', 'ate' all sort to 'aet'.

3Hint 3Explore hint

Use that sorted form as a hash-map key; append each original word to its bucket.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

strs = ["eat","tea","tan","bat"]

eat

sorted → 'aet'

State{aet:[eat]}

Final result[[eat,tea],[tan],[bat]]

C · Code with teaching comments

solution.javaJava

Sorted-Word Key — reference

2 teaching notes

1
public List<List<String>> groupAnagrams(String[] strs) {
2
    Map<String, List<String>> groups = new HashMap<>();
3
    for (String word : strs) {
4
        char[] chars = word.toCharArray();
5
        // Canonicalize the word — anagrams now share an identical char array.
6
        Arrays.sort(chars);
7
        String key = new String(chars);
8
        // Create the bucket if missing, then append the ORIGINAL word.
9
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
10
    }
11
    return new ArrayList<>(groups.values());
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n·k log k) timeO(n·k) spaceOpen the invariant and proofExplore the proof

ComplexityO(n·k log k) time, O(n·k) space — For each of n words we sort k characters (O(k log k)) and do O(1) map work. Total O(n·k log k). We store every word once → O(n·k) space.

E · Edge cases and pitfalls2Storing the sorted key instead of the original word in the bucket.Explore edge cases

Pitfalls

Storing the sorted key instead of the original word in the bucket.
Forgetting computeIfAbsent / defaultdict and NPE-ing on a missing key.

03.2

Approach 2 of 2 · Optimal

Character-Count Key (Optimal)

TimeO(n·k)SpaceO(n·k)

The improvement: replace per-word sorting with O(k) counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Sorting each word costs O(k log k). Can you build a canonical key in O(k)?

2Hint 2Explore hint

Two words are anagrams iff their 26-letter counts match. Use those counts as the key.

3Hint 3Explore hint

Encode the count vector into something hashable — a tuple in Python, a delimited string in Java.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

strs = ["eat","tea","tan"]

Hash-map state

eat

ValueIndex / state

sig(eat)→ [eat]

Continue scanning

new bucket aet-sig

Final result[[eat,tea],[tan]]

C · Code with teaching comments

solution.javaJava

Character-Count Key (Optimal) — optimal

3 teaching notes

1
public List<List<String>> groupAnagrams(String[] strs) {
2
    Map<String, List<String>> groups = new HashMap<>();
3
    for (String word : strs) {
4
        int[] count = new int[26];
5
        for (char c : word.toCharArray()) {
6
            // Build the 26-letter histogram for this word in O(k).
7
            count[c - 'a']++;
8
        }
9
        StringBuilder key = new StringBuilder();
10
        for (int n : count) {
11
            // Delimiter prevents collisions like [1,12] vs [11,2].
12
            key.append(n).append('#');
13
        }
14
        // Bucket by the encoded signature; store the original word.
15
        groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(word);
16
    }
17
    return new ArrayList<>(groups.values());
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n·k) timeO(n·k) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5strs = [""] — Empty word → all-zero count signature → its own single-element group.Explore edge cases

Edge cases handled

strs = [""]Empty word → all-zero count signature → its own single-element group.
strs = ["a","a"]Identical words share a signature → one group ["a","a"].

Pitfalls

Encoding counts without a delimiter — [1,12] and [11,2] can collide into the same string.
Using the raw int[] as a Java map key — arrays use identity equality, so every word becomes its own bucket.
Recomputing the key when retrieving — compute once per word and reuse.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

int[] as a HashMap key in Java

Arrays hash by identity, not contents, so two equal count vectors are treated as different keys and nothing groups. Encode the counts as a String (or use Arrays-based wrappers).

Explore the code comparison

Don't write this

Map<int[], List<String>> groups = new HashMap<>();
groups.computeIfAbsent(count, k -> new ArrayList<>()).add(word);

Write this instead

String key = encode(count); // e.g. join with '#'
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);

Ambiguous count encoding

Concatenating counts without separators makes [1,12] and [11,2] both become "112", merging unrelated groups. Use a delimiter.

Explore the code comparison

Don't write this

for (int n : count) key.append(n); // "112" is ambiguous

Write this instead

for (int n : count) key.append(n).append('#');

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Canonical key + hash-map bucketing

Code pattern to memorize

groups = defaultdict(list)
for word in strs:
    key = canonical(word)   # sorted(word) OR 26-count tuple
    groups[key].append(word)
return list(groups.values())

Rules to remember

1All anagrams must collapse to the same key — sort the word, or use a tuple of 26 counts.
2The count-tuple key is O(k) per word vs O(k log k) for sorting — faster for long words.
3Use the key only to bucket; the stored values are the original words, untouched.
4Pick a key type your map can hash: a string in Java (new String(count)), a tuple in Python.
5Return map.values() — order of groups doesn't matter per the problem.

Use this pattern when

Group / cluster items that share an equivalence (anagram, same digits, same shape)
'Partition this list by some normalized form'
Any time a canonical representative collapses many inputs to one bucket

Choose another pattern when

Just compare two strings → Valid Anagram (no bucketing needed)
Need anagram substrings of a text → sliding-window frequency
Equivalence can't be reduced to a hashable key → may need union-find

Interview takeaway

Bucketing by a canonical key is the go-to for any 'group things that are equivalent' problem. Choosing a cheap, collision-free key (sorted form or count signature) is the whole game.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
The two-word version — compare a single pair instead of bucketing many.
Find All Anagrams in a String
Coming soon
Slide a fixed-size window and compare frequency tables.
Group Shifted Strings
Coming soon
Same bucketing pattern with a shift-difference canonical key.

Same pattern

←

Contains Duplicate

Continue · Next problem

Product of Array Except Self