Group Anagrams
On this page
Problem statement
Given a list of lowercase words, put words that are anagrams of each other into the same group and return the groups. Two words are anagrams if one is a rearrangement of the other's letters ("listen" and "silent"). Groups, and the words inside them, can be returned in any order.
It looks like a string problem, but the real question is a hashing one: what key makes all anagrams collide and nothing else? The same "design a canonical key" idea is used to group log lines, deduplicate records and bucket shapes. Original problem: LeetCode 49.
Example

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] # any order
Input: [""]
Output: [[""]] # the empty string is a valid word
Constraints (assumed)
- 1 ≤ n ≤ 10,000 words.
- 0 ≤ word length ≤ 100, lowercase English letters only.
What this question tests
- Recognizing a grouping problem and reaching for a hash map from key to list.
- Choosing a key that is canonical: equal exactly for anagrams.
- Comparing two keys by cost and explaining which one wins for long words.
Questions to ask first
- Only lowercase a–z? Or Unicode, spaces, capitals? (Here: lowercase only; this decides whether a 26-count key works.)
- Can the list contain duplicates or empty strings? (Here: yes, both go in groups like any other word.)
- Does output order matter? (Here: no.)
- How long can a word be? It decides sorted key versus count key.
Try it first
Before reading on, try it yourself: what could you compute from a word so that "eat", "tea" and "ate" give the same result, and "aab" and "abb" don't? Sketch the key and the complexity, then open the solution.
Approach ladder
Weakcompare every pair of words
For each word, compare it with every existing group's first word using an anagram check (sort both, or count letters). With n words that's O(n²) checks, each O(k) or O(k log k). Fine for ten words, too slow for ten thousand.
Goodsorted letters as the key
Sort each word's letters to get its key ("tea" → "aet") and group with a hash map. Every word is sorted once: O(n · k log k). Short, clear and the answer most interviewers expect first.
Strongletter counts as the key
Count the 26 letters of each word and use the tuple of counts as the key. Building it is O(k), so the total is O(n · k), which beats sorting for long words. Mention both, pick one, and explain the trade-off: the count key needs a fixed alphabet; the sorted key works for any characters.
Solution
Step 1: compute a key that anagrams share

Two words are anagrams exactly when they have the same letters with the same counts. Sorting the letters puts them in a fixed order, so equal multisets give equal strings.
Step 2: group by key
Append each word to groups[key], then return all the lists.
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w)
return list(groups.values())
List<List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
char[] chars = w.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(groups.values());
}
vector<vector<string>> groupAnagrams(const vector<string>& words) {
unordered_map<string, vector<string>> groups;
for (const string& w : words) {
string key = w;
sort(key.begin(), key.end());
groups[key].push_back(w);
}
vector<vector<string>> out;
for (auto& [key, g] : groups) out.push_back(g);
return out;
}
func groupAnagrams(words []string) [][]string {
groups := make(map[string][]string)
for _, w := range words {
b := []byte(w)
sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
key := string(b)
groups[key] = append(groups[key], w)
}
out := make([][]string, 0, len(groups))
for _, g := range groups {
out = append(out, g)
}
return out
}
Time: O(n · k log k) for sorting each word. Space: O(n · k) for the keys and groups.
The count-key version, for when words are long:
def group_anagrams_counts(words):
groups = defaultdict(list)
for w in words:
count = [0] * 26
for ch in w:
count[ord(ch) - ord('a')] += 1
groups[tuple(count)].append(w) # lists can't be keys; tuples can
return list(groups.values())
Time: O(n · k). In Java or Go, turn the counts into a string such as "1#0#0#…" (or use a fixed-size array as a Go map key: [26]int is comparable).
The common bug

The tempting shortcut is a key that loses information: the set of letters, or the sum of character codes. "aab" and "abb" have the same set {a, b}, and different words can share a character-code sum. The key must capture letter counts exactly: a sorted string or a full count vector. A related slip in Python is using a list as a dictionary key, which raises TypeError; convert it to a tuple.
Edge cases
- Empty string: its key is
""; it forms its own group. - Duplicates:
["a", "a"]→ one group["a", "a"]. - Single word: one group.
- No anagrams at all: n groups of one.
- Very long words: prefer the count key, O(k) instead of O(k log k).
Variants seen in interviews
- Valid Anagram (are two strings anagrams?): compare counts. See Valid Anagram.
- Find all anagrams of a pattern inside a long string: a fixed-size sliding window with counts. See Permutation in String.
- Group shifted strings ("abc", "bcd", "xyz"): the key is the list of gaps between consecutive letters.
- Group by any equivalence (same digits, same set of tags): the same "canonical key + hash map" recipe.
- Return only the largest group or the number of groups.
Follow-up questions
- The words contain Unicode characters. Which key still works, and what does it cost?
- What is the complexity of each key choice, and when does the count key win?
- Could you use a product of primes as the key? What goes wrong?
- There are billions of words spread over many machines. How would you group them? (Hint: partition by key.)
- How would you return the groups sorted by size, largest first?
- How would you check, in O(1) extra space, whether two given words are anagrams?
Related
- Patterns: Hash Maps and Prefix Sums, Sliding Window (for the find-all-anagrams variant)
- Similar problems: Valid Anagram, Two Sum, Top K Frequent Elements, Permutation in String
- Data structures: Hash Maps, Arrays and Strings