Approach Summary
Sort each string to get its canonical form. Group strings with the same sorted form using a hash map.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sorted String as Hash Map Key | O(N * K log K) | O(N * K) | Sort each word alphabetically to create a canonical anagram key in O(N * K log K). |
| 2 Approach 2: Character Count Signature (Optimal) | O(N * K) | O(N * K) | Encode 26-character frequency counts into a delimiter-separated string key in O(N * K). |
Step 1: Baseline
Approach 1: Sorted String as Hash Map Key
Time: O(N * K log K)
Space: O(N * K)
For each word in strs, sort its characters alphabetically (e.g. "tea" -> "aet", "ate" -> "aet"). Words that are anagrams produce the exact same sorted string. Use this sorted string as the key in a hash map and append the original word to the list corresponding to that key.
Approach 1: Sorted String as Hash Map Key Implementation
Approach 1: Sorted String as Hash Map Key
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String key = String.valueOf(ca);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}
}class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (string& s : strs) {
string key = s;
sort(key.begin(), key.end());
map[key].push_back(s);
}
vector<vector<string>> res;
for (auto& p : map) res.push_back(p.second);
return res;
}
};class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
groups = {}
for s in strs:
key = "".join(sorted(s))
if key not in groups:
groups[key] = []
groups[key].append(s)
return list(groups.values())function groupAnagrams(strs) {
const map = new Map();
for (const s of strs) {
const key = s.split('').sort().join('');
if (!map.has(key)) map.set(key, []);
map.get(key).push(s);
}
return Array.from(map.values());
} Step 2: Most Optimized
Approach 2: Character Count Signature (Optimal)
Time: O(N * K)
Space: O(N * K)
Instead of sorting strings, construct a 26-element array counting character frequencies. Convert the array into a hashable key with delimiters (e.g. "1#0#0#...#1#"). All anagrams have the identical frequency signature. This avoids the O(K log K) sorting overhead.
Approach 2: Character Count Signature (Optimal) Implementation
Approach 2: Character Count Signature (Optimal)
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groupAnagrams = new HashMap<>();
for (String word : strs) {
int charCount[] = new int[26];
for (char c : word.toCharArray()) {
charCount[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int charVal : charCount) {
sb.append(charVal).append("#");
}
String key = sb.toString();
groupAnagrams.putIfAbsent(key, new ArrayList<>());
groupAnagrams.get(key).add(word);
}
return new ArrayList<>(groupAnagrams.values());
}
}class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> anagramGroup;
for (const string& str : strs) {
vector<int> charCount(26, 0);
for (char c : str) charCount[c - 'a']++;
string key;
for (int val : charCount) key += to_string(val) + "#";
anagramGroup[key].push_back(str);
}
vector<vector<string>> result;
for (auto& x : anagramGroup) result.push_back(x.second);
return result;
}
};class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
groups = {}
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
key = tuple(count)
if key not in groups:
groups[key] = []
groups[key].append(s)
return list(groups.values())function groupAnagrams(strs) {
const groups = new Map();
for (const s of strs) {
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
}
const key = count.join('#');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return Array.from(groups.values());
}Edge Cases to Watch
- Empty string in input (strs = [""]; returns [[""]])
- Single character strings (strs = ["a"]; returns [["a"]])
- All words are anagrams of each other (grouped into single list)
- No words are anagrams of each other (each word in its own singleton list)
Algorithmic Pattern
View Pattern Guide →
Master the Hash Map / Set Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Hash Map / Set pattern.
Framework: Hash Map / Set • Interview Prep: Tested at FAANG •
Explore all Hash Map / Set problems & invariants →
How to Recognize This Pattern
- Group strings that are anagrams
- Canonical key per anagram group
Complexity Analysis
Time Complexity
O(n · k log k)
Space Complexity
O(n · k)
Tags
String Hash Map Sorting
Frequently Asked Questions
What is the optimal time and space complexity for Group Anagrams?
The optimal solution for Group Anagrams achieves O(n · k log k) runtime complexity and requires O(n · k) auxiliary space. Time complexity for the frequency-key approach is O(N * K) because counting characters takes linear time in the string length without any sorting. Space complexity is O(N * K) to store all strings inside the hash map groups.
How do I identify that Group Anagrams requires the Hash Map / Set pattern?
In technical interviews, look for key problem signals: Group strings that are anagrams; Canonical key per anagram group. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Hash Map / Set strategy.
What critical edge cases must be handled in Group Anagrams?
Essential edge cases to verify include: Empty string in input (strs = [""]; returns [[""]]); Single character strings (strs = ["a"]; returns [["a"]]); All words are anagrams of each other (grouped into single list); No words are anagrams of each other (each word in its own singleton list). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Group Anagrams?
Group Anagrams is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft, Uber.