Group Anagrams is Day 5 of the Tekraze DSA series, and it is the first problem where you have to build the hash map key yourself. In Day 3, Contains Duplicate, we used a set to spot repeats, and in Day 1, Two Sum, a hash map gave us instant lookups.
Today we push the idea one step further. Instead of storing numbers as keys, we build a smart key that describes a whole word, so every anagram lands in the same bucket.
Also Read: DSA Series Day 4: Valid Anagram in Java, Python and Rust
What is the Group Anagrams problem?
You get an array of strings strs. Group the anagrams together and return the groups in any order. Two words are anagrams when they use exactly the same letters the same number of times. Assume every string contains only lowercase English letters.
On LeetCode this is problem 49, a medium level question. The input has at most 10,000 words and each word is at most 100 letters long.
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Input: strs = [""] Output: [[""]]
How should you think about it in plain words?
Imagine sorting mail into pigeonholes. Every word needs a label so that all anagrams get the same label and nothing else does. Once you have that label, a hash map does the sorting for you. The label is the key and the list of words is the value.
So the real question in Group Anagrams is how to build the label. There are two good answers, the sorted word or the count of each letter.
Three ways to solve Group Anagrams
Here are the three Group Anagrams approaches, from slowest to fastest. Start with the first so you understand why the other two exist.
Solution 1: Brute force comparison
The naive way to solve Group Anagrams is to compare every word with every other word using the anagram check from Day 4, and put matching words into the same group. With n words of length k, that is about n² comparisons, each costing O(k), so O(n² · k) time. It works for tiny inputs and falls over quickly.
Solution 2: Group Anagrams with a sorted key
A much better first answer is to use the sorted word as the key. The words eat, tea and ate all become aet.
python
from collections import defaultdict
def group_anagrams_sort(strs):
groups = defaultdict(list)
for s in strs:
groups["".join(sorted(s))].append(s)
return list(groups.values())
Time is O(n · k log k) because each word gets sorted. Space is O(n · k) to store all the words and keys. This is short, clear and accepted in most interviews.
Solution 3: Group Anagrams with a letter count key (optimal)
Skip the sort. Count the letters of each word into an array of 26 numbers and use that array as the key. Anagrams always produce the same 26 counts. In Python the array becomes a tuple, in Java we turn it into a string, and in Rust a fixed size array can be a map key directly.
Time is O(n · k), one pass over every character plus 26 slots per word. Space is O(n · k) for the map. When words are long, removing that log k factor matters. If you want a refresher on why O(n · k) beats O(n · k log k), read our Big O helper post on time and space complexity.
The table below puts the three Group Anagrams approaches side by side.
| Approach | Time | Space | Best for |
|---|---|---|---|
| Brute force | O(n² · k) | O(n · k) | Understanding the problem |
| Sorted key | O(n · k log k) | O(n · k) | Quick answer under interview pressure |
| Letter count key | O(n · k) | O(n · k) | Long words, the optimal answer |
Group Anagrams code in Java, Python and Rust
All three Group Anagrams programs below use the letter count key. Each one has the same five tests built in, so you can paste it and run it.
Java solution
java
import java.util.*;
public class Solution {
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
String key = Arrays.toString(count);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
// Sort words inside each group and the groups themselves so output is easy to compare
static List<List<String>> normalize(List<List<String>> groups) {
List<List<String>> out = new ArrayList<>();
for (List<String> g : groups) { List<String> c = new ArrayList<>(g); Collections.sort(c); out.add(c); }
out.sort(Comparator.comparing(Object::toString));
return out;
}
public static void main(String[] args) {
String[][] tests = {{"eat", "tea", "tan", "ate", "nat", "bat"}, {""}, {"a"}, {"abc", "def"}, {"ab", "ba", "ab"}};
String[] expected = {"[[ate, eat, tea], [bat], [nat, tan]]", "[[]]", "[[a]]", "[[abc], [def]]", "[[ab, ab, ba]]"};
for (int i = 0; i < tests.length; i++) {
String got = normalize(groupAnagrams(tests[i])).toString();
System.out.println((got.equals(expected[i]) ? "PASS " : "FAIL ") + got);
}
}
}
Python solution
python
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
groups[tuple(count)].append(s)
return list(groups.values())
if __name__ == "__main__":
tests = [
(["eat", "tea", "tan", "ate", "nat", "bat"], [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]),
([""], [[""]]),
(["a"], [["a"]]),
(["abc", "def"], [["abc"], ["def"]]),
(["ab", "ba", "ab"], [["ab", "ab", "ba"]]),
]
for strs, want in tests:
got = sorted(sorted(g) for g in group_anagrams(strs))
print("PASS" if got == want else "FAIL", got)
Rust solution
rust
use std::collections::HashMap;
fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let mut groups: HashMap<[u16; 26], Vec<String>> = HashMap::new();
for s in strs {
let mut count = [0u16; 26];
for b in s.bytes() {
count[(b - b'a') as usize] += 1;
}
groups.entry(count).or_default().push(s);
}
groups.into_values().collect()
}
fn main() {
let tests: Vec<(Vec<&str>, Vec<Vec<&str>>)> = vec![
(vec!["eat", "tea", "tan", "ate", "nat", "bat"], vec![vec!["ate", "eat", "tea"], vec!["bat"], vec!["nat", "tan"]]),
(vec![""], vec![vec![""]]),
(vec!["a"], vec![vec!["a"]]),
(vec!["abc", "def"], vec![vec!["abc"], vec!["def"]]),
(vec!["ab", "ba", "ab"], vec![vec!["ab", "ab", "ba"]]),
];
for (input, want) in tests {
let mut got = group_anagrams(input.iter().map(|s| s.to_string()).collect());
for g in got.iter_mut() { g.sort(); }
got.sort();
let ok = got.iter().map(|g| g.iter().map(|s| s.as_str()).collect::<Vec<_>>()).collect::<Vec<_>>() == want;
println!("{} {:?}", if ok { "PASS" } else { "FAIL" }, got);
}
}
The groups can come back in any order, so each test sorts the words inside every group and then sorts the groups before comparing. The five tests are the classic example, a single empty string, a single letter, two words with no anagrams, and duplicate words. [VERIFY BEFORE PUBLISHING: confirm the Rust run on your machine]
What are the tips and tricks for an easy solution?
Spot the pattern. Whenever a problem says group, bucket or classify things that are the same in some way, think of a hash map with a well chosen key. Group Anagrams is the textbook example.
Ask what makes two items equal. Build a key that captures exactly that. Here it is letter frequency, and order does not matter.
Start with the sorted key. It is the easiest version to write under pressure. Mention the counting key as the upgrade.
Make the key hashable. Python lists cannot be dict keys, so use a tuple. In Java, raw arrays compare by reference, so convert to a string.
Mind your separators. If you build a string key by joining counts, put a separator between them, otherwise counts like 1 and 11 can blur together. Arrays.toString does this for you.
Handle the edges. Empty strings are anagrams of each other, and duplicate words belong in the same group.
What are the common mistakes people make in Group Anagrams?
- Using a Java
int[]directly as a map key, which never matches because arrays use identity equality. - Trying to use a Python list as a dictionary key and getting a
TypeError. - Joining counts without a separator, which can create false matches between different words.
- Assuming the groups must come back in a fixed order and failing tests that compare raw output.
Where is this pattern used in the real world?
Grouping by a computed key is everywhere, and Group Anagrams is the small version of it. Databases do it with GROUP BY, log tools group error messages by a cleaned up signature, photo apps group duplicate images by a fingerprint hash, and search engines group near identical pages. Word games and spell checkers literally group words by their letters to suggest anagrams.
Which earlier posts in the series should you read?
Start with Day 1, Two Sum for the basic hash map lookup, then Day 2, Best Time to Buy and Sell Stock for single pass thinking, and Day 3, Contains Duplicate to see how a set catches repeats. Day 4, Valid Anagram, gives you the letter counting idea that today’s key is built on. Today’s Group Anagrams problem combines all of that.
Frequently asked questions
What is the best approach for Group Anagrams?
Use a hash map where the key is a count of the 26 letters in each word. That runs in O(n · k) time, where n is the number of words and k is the longest word.
Is using the sorted word as a key good enough?
Yes. It is correct and easy to explain, and runs in O(n · k log k). The counting key is only faster when words are long.
Why can’t I use an int array as a key in Java?
Java arrays use reference equality, so two arrays with the same values are still different keys. Convert the array to a string first.
Does the order of the groups matter in Group Anagrams?
No. The problem accepts the groups and the words inside them in any order.
Is Group Anagrams asked in coding interviews?
Yes, it is a very common medium level question and a natural follow up to Valid Anagram.
Conclusion
Group Anagrams comes down to one decision: what key describes a word so that all anagrams share it. Start with the sorted key, then upgrade to the 26 letter count key when you need O(n · k). Next in the series we move on to the two pointer pattern, so make sure grouping with a hash map feels natural first.
