Group Anagrams

Problem in Plain English

Given an array of strings, group the anagrams together so that strings which are rearrangements of each other share one group. The groups may be returned in any order.

Problem Statement

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

An anagram is a word formed by rearranging the letters of another word, so every anagram in one group shares the same character frequencies. Mapping each string to a canonical signature lets a hash map collect the groups in one pass.

Constraints

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

Examples

Example 1

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

ate, eat, and tea share one a, one e, and one t, so they land in the same group. tan and nat share a, n, t; bat has no partner. Group order and word order within a group do not affect correctness.

Example 2

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

An empty string is an anagram of itself and forms a group of one.

Example 3

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

A single character is an anagram of itself and forms a group of one.

Example 4

Input: strs = ["ab", "aab", "aba", "ab"]
Output: [["ab", "ab"], ["aab", "aba"]]

ab has one a and one b; aab and aba each have two a characters and one b. Different letter multiplicities create separate groups, while both occurrences of ab remain in their group.

Intuition

Give every word a label that ignores letter order but preserves how many of each letter it contains. In Example 1, eat, tea, and ate all have one a, one e, and one t; tan and nat share a different label. A hash map stores each label with its original words. Sorting produces a readable label, while counting the 26 possible letters avoids sorting.

Approaches

Sorted Key Grouping

Solution Details

Reveal Sorted Key Grouping: intuition, complexity, and code

Intuition

Sorting the letters of each string gives every anagram the same canonical key, so a hash map from sorted key to list collects the groups. Sorting each word costs extra time, which is the bottleneck the counting approach later removes.

Step-by-Step Logic

Create an empty map from a sorted-letter key to a list of original strings.
For every string, copy its letters and sort the copy. In Example 1, eat becomes aet, tea becomes aet, and tan becomes ant.
If the key has no list yet, create one. Append the original string to that list, preserving every occurrence; do not append the sorted key.
Continue for all strings: ate joins aet, nat joins ant, and bat starts abt.
Return the map's lists. Here they contain [eat, tea, ate], [tan, nat], and [bat], equivalent to Example 1's output in another allowed order.

Why It Works

Sorting preserves every letter and its multiplicity. Two sorted strings are equal exactly when their original strings contain the same letter counts, so they are anagrams exactly when their keys match. After each insertion, every processed occurrence appears once in its correct group; returning all map values therefore loses and merges no words.

Dry Run

Sorted Key Grouping: variable states at each step
string	sorted key	group after insert
`"eat"`	`"aet"`	`["eat"]`
`"tea"`	`"aet"`	`["eat", "tea"]`
`"tan"`	`"ant"`	`["tan"]`
`"ate"`	`"aet"`	`["eat", "tea", "ate"]`
`"nat"`	`"ant"`	`["tan", "nat"]`
`"bat"`	`"abt"`	`["bat"]`, all groups `["bat"], ["tan", "nat"], ["eat", "tea", "ate"]`

Complexity Analysis

Time Complexity

O(m k log k)

Space Complexity

O(m k)

Let m be the number of words and k be the larger of 2 and the maximum word length, so empty words still incur map work. Sorting costs O(k log k) per word and key hashing costs O(k), with expected constant-time map access. At most m keys of length k and m output references are stored; the temporary letter copy uses O(k). Input strings are referenced, not copied into each group.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<List<String>> groupAnagrams(String[] strs) {5        Map<String, List<String>> map = new HashMap<>();6        for (String s : strs) {7            char[] chars = s.toCharArray();8            Arrays.sort(chars);9            String key = new String(chars);10            map.putIfAbsent(key, new ArrayList<>());11            map.get(key).add(s);12        }13        return new ArrayList<>(map.values());14    }15}

Hints

Hint 1

Ask what single value would be identical for all anagrams of one word but different across groups.

Hint 2

Sorting each word produces such a canonical key and pairs with a hash map from key to list.

Hint 3

With only 26 lowercase letters, a character frequency fingerprint works as the key in linear time per word.

Edge Cases

Empty strings such as ["", ""] share one fingerprint and must land in a single group.
Single-character strings each form a group keyed by their one count without any indexing errors.
Inputs where nothing is an anagram of anything else produce one single-element group per string.
Repeated words such as [eat, eat, tea] remain three occurrences in one group; grouping must not deduplicate them.
Repeated letters matter: abb and ab have different count vectors and must remain separate.

Common Mistakes and Interview Tips

Using a raw array as a map key in JavaScript, where keys compare by reference, so equal fingerprints never match; join the counts into a string first.
Building the frequency key without a delimiter, so different count vectors can collide into the same key string.
Interview tip: clarify the alphabet before proposing 26 slots. Arbitrary Unicode requires a different signature; the fixed lowercase alphabet is what makes counting cheaper here.

Key Takeaway

When items that are rearrangements of each other must be grouped, map each item to one canonical signature and collect the groups in a hash map.