Group Anagrams — Canonical Keys and the Group-By Pattern

Problem Statement#

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word formed by rearranging the letters of a different word, using all the original letters exactly once.

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Example 1:
Input:  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

Example 2:
Input:  strs = [""]
Output: [[""]]

Example 3:
Input:  strs = ["a"]
Output: [["a"]]

Why This Problem Matters#

Group Anagrams is one of the most important medium problems for interviews because it tests the canonical-key pattern — the idea that different objects can be grouped together if they share an invariant representation. Two words are anagrams if they share the same sorted character form (or the same character frequency signature). By computing a canonical key for each word and using it as a HashMap key, you group all anagrams in O(n k log k) time (or O(n k) with the count-based key).

Amazon includes this problem in its loop interviews because it mimics real-world data pipeline tasks: grouping log messages by a normalized key, clustering product names by phonetic similarity, or deduplicating events by their canonical form. The conceptual jump from "compare all pairs" (O(n^2)) to "compute a canonical key and group" (O(n)) is the same insight used in distributed systems to scale data processing.

Google and Meta ask this problem to see if you know both approaches — the sort-based key (simpler but O(k log k) per word) and the count-based key (O(k) per word but slightly more complex implementation). The count-based approach avoids sorting altogether, turning a sub-optimal key computation into a linear one. Candidates who offer both approaches and articulate the trade-off demonstrate strong algorithmic thinking.

This problem also appears as a component in harder problems: finding groups of related strings, clustering similar inputs, or detecting encoding similarities. Internalizing the "canonical key → group" pattern is essential before tackling those harder variants.

The Core Insight#

Two words are anagrams if and only if they have identical character multisets. There are two canonical ways to represent a character multiset:

Approach 1 — Sorted string key: Sort the characters of each word. All anagrams produce the same sorted string. Use the sorted string as the HashMap key. Time per word: O(k log k) for sorting.

Approach 2 — Character count tuple key: Count character frequencies in a fixed-size 26-element array. Represent this array as a tuple. All anagrams produce the same count tuple. Use the tuple as the HashMap key. Time per word: O(k) for counting.

Both approaches give the same overall grouping result. The sort-based approach is simpler to implement; the count-based approach is faster when words are long. For the given constraints (words up to 100 characters), both are fast enough, but the count-based approach demonstrates deeper understanding in an interview.

The algorithm in both cases:

1. For each word, compute its canonical key.
2. Append the word to groups[key].
3. Return the values of groups as the result.

Visual Dry Run#

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

Sort-based key approach:

Result: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Count-based key for "eat":

Frequency array: [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] (a=1, e=1, t=1, all others 0)

As a tuple: (1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0)

"tea" and "ate" produce the same tuple → they all land in the same group.

Solution (Optimal)#

from collections import defaultdict
 
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    # Sort-based key: O(n * k log k)
    groups = defaultdict(list)
    for word in strs:
        key = tuple(sorted(word))  # Canonical anagram key
        groups[key].append(word)
    return list(groups.values())
 
 
def groupAnagrams_count_key(strs: list[str]) -> list[list[str]]:
    # Count-based key: O(n * k) — faster for long words
    groups = defaultdict(list)
    for word in strs:
        count = [0] * 26
        for ch in word:
            count[ord(ch) - ord('a')] += 1
        key = tuple(count)  # 26-element tuple as HashMap key
        groups[key].append(word)
    return list(groups.values())

var groupAnagrams = function(strs) {
    const groups = new Map();
 
    for (const word of strs) {
        // Sort-based canonical key
        const key = [...word].sort().join('');
 
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(word);
    }
 
    return [...groups.values()];
};
 
 
// Count-based key variant
var groupAnagrams_count = function(strs) {
    const groups = new Map();
 
    for (const word of strs) {
        const count = new Array(26).fill(0);
        for (const ch of word) {
            count[ch.charCodeAt(0) - 97]++;
        }
        const key = count.join(',');  // Serialize count array as string key
 
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(word);
    }
 
    return [...groups.values()];
};

Complexity Analysis

The count-based key is asymptotically better for long words. In practice, for k ≤ 100 (the constraint), the difference is negligible. Mention both approaches in the interview and let the interviewer choose which to implement.

Common Mistakes#

• Using a list as a HashMap key in Python. Lists are not hashable. Use tuple(sorted(word)) or tuple(count_array) as the key, not a list.
• Using the word itself as the key. The whole point is to find a key that is equal for anagrams. Using the word as the key groups each word with itself only.
• Forgetting defaultdict and crashing on first insertion. Without defaultdict(list), groups[key].append(word) fails if key is new. Use defaultdict or check if key not in groups: groups[key] = [].
• Returning grouped pairs instead of grouped lists. The output should be a list of lists, not a list of tuples.
• Sorting in place. word.sort() does not work because strings are immutable in Python (and JavaScript). Use sorted(word) which returns a new sorted list.
• Using ''.join(sorted(word)) vs tuple(sorted(word)) as keys. Both work as Python dict keys. The joined string is more readable; the tuple is slightly more memory-efficient for short keys.

Follow-up Questions#

What is the minimum possible time complexity for this problem? You must at minimum read every character of every word to compute any canonical key, giving O(n * k) as a lower bound. The count-based approach achieves this lower bound.

What if words can contain Unicode characters (not just lowercase ASCII)? Replace the 26-element count array with a hash map from character to count. The algorithm is otherwise identical. The key becomes a frozen dictionary (Python: frozenset(Counter(word).items())).

How would you find the largest anagram group? After grouping, return max(groups.values(), key=len). This is O(n) over the groups, which is dominated by the grouping step.

Can you group anagrams without a hash map? Sort the entire list of words using (sorted_word, original_word) as the sort key. Equal sorted forms will be adjacent. Then collect adjacent equal groups. Time is O(n k log n) for the outer sort.

How does this extend to grouping by other canonical properties? The same pattern applies to any equivalence class. To group palindromes: use the canonical form after the palindrome normalization. To group by phonetic similarity: use a Soundex or Metaphone encoding as the key. The grouping mechanism is the same.

Key Takeaways#

• LC 49 Group Anagrams is the canonical "group by canonical key" hashmap pattern.
• Two strings are anagrams iff they share the same multiset of letters; pick a canonical representative for that multiset.
• The sorted-string key gives O(N * K log K); the 26-element frequency tuple gives O(N * K) — pick by alphabet size.
• Use defaultdict(list) (Python) or a Map of arrays (JavaScript) to bucket strings by key.
• Tuple-of-counts works as a dict key in Python (tuple(counts)); in JS, build a delimited string like "1#0#2#...".
• This same "group by canonical form" pattern powers plagiarism detection, near-duplicate clustering, and SQL GROUP BY.
• Watch out for unicode — for arbitrary characters use a Counter hashed to a tuple of (char, count) pairs sorted lexicographically.

Related Problems#

• LC 49 — Group Anagrams: This problem.
• LC 242 — Valid Anagram: Check if exactly two strings are anagrams — simpler version of the same frequency comparison.
• LC 438 — Find All Anagrams in a String: Sliding window variant — check anagrams within a larger string.
• LC 1002 — Find Common Characters: Frequency intersection across multiple strings.
• LC 347 — Top K Frequent Elements: Group by frequency, then retrieve top k — same "group by property" pattern.
• LC 953 — Verifying an Alien Dictionary: Uses a custom comparison key (alien alphabet ordering) for grouping/sorting.