📚 Table of Contents
📋 Problem Statement
Given an array of strings, cluster words that share identical character counts. Words in same cluster are anagrams.
Examples
Example 1:
Input: ["eat","tea","tan","ate","nat","bat"]Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Example 2:
Input: [""]Output: [[""]]
Constraints
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]consists of lowercase English letters
🎯 Real-World Analogy
Sorting Keys for Lockers
Two keys belong in same locker if they have exactly the same tooth pattern, even if teeth appear in different order when drawn as strings.
Build a canonical signature per word, and use that signature as locker ID.
💡 Key Insights
- Anagrams share the same normalized signature.
- Signature options: sorted string or 26-count frequency tuple.
- Hash map from signature -> list of words is the core data structure.
- Frequency tuple avoids O(K log K) per string sort.
- Output order across groups is not required unless explicitly stated.
💻 Solution Approaches
Approach 1: Sorted-String Signature
Time: O(N * K log K) | Space: O(N * K)
Simple and readable. Sort each word to get canonical key.
Approach 2: Frequency Signature (Recommended)
Time: O(N * K) | Space: O(N * K)
Build 26-length count vector per word and use it as map key.
Python Implementation
from collections import defaultdict
from typing import List
def group_anagrams(strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in strs:
counts = [0] * 26
for ch in word:
counts[ord(ch) - ord('a')] += 1
key = tuple(counts)
groups[key].append(word)
return list(groups.values())
JavaScript Implementation
function groupAnagrams(strs) {
const groups = new Map();
for (const word of strs) {
const counts = new Array(26).fill(0);
for (const ch of word) {
counts[ch.charCodeAt(0) - 97] += 1;
}
const key = counts.join("#");
if (!groups.has(key)) {
groups.set(key, []);
}
groups.get(key).push(word);
}
return Array.from(groups.values());
}
🔍 Step-by-Step Walkthrough
Trace ["eat","tea","tan","ate","nat","bat"]:
"eat" -> signature for a,e,t -> group 1 starts.
"tea" and "ate" produce same signature -> append to group 1.
"tan" and "nat" share another signature -> group 2.
"bat" unique signature -> group 3. Return all groups.
⚡ Complexity Analysis
Time Complexity: O(N * K)
- N words, each of length K on average.
- Frequency signature builds in O(K).
- Hash map insert is O(1) average per word.
Space Complexity: O(N * K)
- Need storage for grouped output strings.
- Map keys for distinct signatures also consume space.
🔧 Edge Cases
- Empty string entries
- Single-word input
- All words are same anagram group
- No anagrams at all
- Duplicate strings should stay duplicated in output group
🧪 Test Cases
Python
def normalize(groups):
return sorted(sorted(g) for g in groups)
def test_group_anagrams():
out1 = group_anagrams(["eat","tea","tan","ate","nat","bat"])
assert normalize(out1) == normalize([["eat","tea","ate"],["tan","nat"],["bat"]])
assert group_anagrams([""]) == [[""]]
assert group_anagrams(["a"]) == [["a"]]
out4 = group_anagrams(["ab","ba","ab"])
assert normalize(out4) == normalize([["ab","ba","ab"]])
print("✅ all tests passed")
JavaScript
function testGroupAnagrams() {
const out = groupAnagrams(["eat","tea","tan","ate","nat","bat"]);
console.assert(out.length === 3, "test 1");
console.assert(JSON.stringify(groupAnagrams([""])) === JSON.stringify([[""]]), "test 2");
console.assert(JSON.stringify(groupAnagrams(["a"])) === JSON.stringify([["a"]]), "test 3");
console.log("✅ all tests passed");
}
💼 Interview Tips
- Start with sorted-key solution, then optimize to frequency-key if needed.
- Explain why signatures are collision-free for lowercase letters.
- Discuss output-order flexibility when problem says "any order".
- Mention tradeoff: tuple counts faster than sorting for long strings.
- Keep map value as array and append incrementally.
🎓 Key Takeaways
- Canonical signatures make grouping problems straightforward.
- Hash maps + normalization is the core pattern for anagram families.
- Frequency keys can reduce per-string overhead versus sorting.