Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Group strings by their anagram equivalence class — using a sorted key and a hash map.
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
"bat"."nat" and "tan" are anagrams as they can be rearranged to form each other."ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] consists of lowercase English letters.The naive approach: for each pair of strings, check if they're anagrams (same character counts). Group matching strings together.
For n strings, we'd need to compare every pair — that's O(n^2) comparisons, each taking O(k) time to check character counts.
Total: O(n^2 * k) time. We also need a union-find or visited set to form groups. This is slow and complicated.
Better idea: Instead of comparing strings to each other, compute a canonical form for each string that's the same for all anagrams. Then just group by canonical form using a hash map — one pass!
Two strings are anagrams if and only if they contain the same characters in the same frequencies. Sorting a string produces a canonical form that's identical for all anagrams.
Same sorted form = same anagram group. Use sorted string as the HashMap key.
Instead of sorting, count character frequencies and use the count array as the key. This avoids the O(k log k) sort cost.
// Example: "eat" → "1#0#0#0#1#...#1#0#..." (counts of a,b,c,...) int[] count = new int[26]; for (char c : s.toCharArray()) count[c - 'a']++; String key = Arrays.toString(count); // Use as HashMap key
// Example: "eat" → [1,0,0,0,1,...,1,0,...] (counts of a,b,c,...) var count [26]int for _, c := range s { count[c-'a']++ } key := count // Use as map key (arrays are comparable in Go)
# Example: "eat" → (1, 0, 0, 0, 1, ..., 1, 0, ...) (counts of a,b,c,...) count = [0] * 26 for c in s: count[ord(c) - ord('a')] += 1 key = tuple(count) # Use as dict key
// Example: "eat" → [1,0,0,0,1,...,1,0,...] (counts of a,b,c,...) let mut count = [0u8; 26]; for b in s.bytes() { count[(b - b'a') as usize] += 1; } let key = count; // Use as HashMap key (arrays implement Hash+Eq)
// Example: "eat" → "1#0#0#0#1#...#1#0#..." (counts of a,b,c,...) const count = new Array(26).fill(0); for (const c of s) count[c.charCodeAt(0) - 97]++; const key = count.join('#'); // Use as Map key
This runs in O(k) per string instead of O(k log k), but the key string is longer (26 numbers). Both approaches work well in practice.
Hash maps turn grouping into a single pass. For each string: compute key, look up in map, append to group list. No pair comparisons needed. The map does the grouping automatically.
Let's process ["eat","tea","tan","ate","nat","bat"] one string at a time and watch the HashMap build up.
Return the values: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
"". Result: [["]]. Works naturally."a". Result: [["a"]]."". Result: [["",""]]. They are anagrams of each other.class Solution { public List<List<String>> groupAnagrams(String[] strs) { // Key: sorted string, Value: list of original strings Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { // Compute canonical form by sorting characters char[] chars = s.toCharArray(); Arrays.sort(chars); String key = new String(chars); // Add to the bucket for this key // computeIfAbsent creates the list if key is new map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); } // Return all bucket values as a list of lists return new ArrayList<>(map.values()); } }
func groupAnagrams(strs []string) [][]string { // Key: sorted-char array (comparable), Value: list of original strings groups := make(map[[26]int][]string) for _, s := range strs { // Compute canonical form: count character frequencies var key [26]int for _, c := range s { key[c-'a']++ } // Add to the bucket for this key groups[key] = append(groups[key], s) } // Return all bucket values as a slice of slices result := make([][]string, 0, len(groups)) for _, v := range groups { result = append(result, v) } return result }
def group_anagrams(strs: list[str]) -> list[list[str]]: # Key: sorted string, Value: list of original strings groups: dict[str, list[str]] = {} for s in strs: # Compute canonical form by sorting characters key = "".join(sorted(s)) # Add to the bucket for this key # setdefault creates the list if key is new groups.setdefault(key, []).append(s) # Return all bucket values as a list of lists return list(groups.values())
use std::collections::HashMap; impl Solution { pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> { // Key: sorted-char array, Value: list of original strings let mut map: HashMap<[u8; 26], Vec<String>> = HashMap::new(); for s in strs { // Compute canonical form: count character frequencies let mut key = [0u8; 26]; for b in s.bytes() { key[(b - b'a') as usize] += 1; } // Add to the bucket for this key map.entry(key).or_default().push(s); } // Return all bucket values as a Vec of Vecs map.into_values().collect() } }
function groupAnagrams(strs: string[]): string[][] { // Key: sorted string, Value: list of original strings const map = new Map<string, string[]>(); for (const s of strs) { // Compute canonical form by sorting characters const key = s.split('').sort().join(''); // Add to the bucket for this key if (!map.has(key)) map.set(key, []); map.get(key)!.push(s); } // Return all bucket values as a list of lists return [...map.values()]; }
Enter comma-separated strings and step through the grouping process. Watch the hash map build up entry by entry.
We process n strings. For each string of length k, sorting takes O(k log k). HashMap operations are O(k) amortized (for hashing the key). Total: O(n × k log k). Space stores all strings in the map: O(n × k) for the keys and value lists.
Compare every pair of n strings to check if they are anagrams. Each comparison builds two frequency arrays of size 26 and compares them in O(k) time. With n(n-1)/2 pairs, total work is O(n2 × k). A union-find or visited set is also needed to form groups.
One pass over n strings: sort each string's characters in O(k log k) to produce a canonical key, then insert into a HashMap in O(k) amortized time. The map stores all n strings and their keys, using O(n × k) space. Using a character-count key reduces time to O(n × k).
Sorting each string gives a canonical key -- all anagrams produce the same sorted string. Alternative: use a character count array as the key for O(n × k) time, avoiding the O(k log k) sort. In practice, the sort approach is simpler and fast enough for typical string lengths.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.