Group Anagrams: 3 Hash Map Approaches (Sorted, Count, Prime)

You solve "Group Anagrams" with sorted strings. It works, but is there a better way?

Yes. There are 3 approaches, each with different trade-offs.

This guide shows you all three and when to use each.

Approach 1: Sorted String as Key

The approach

Sort each word, use sorted string as key.

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        key = ''.join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

Complexity

Time: O(n × k log k) where n = words, k = max word length
Space: O(n × k)

Pros/Cons

✅ Pros:

• Simple and intuitive
• Works for any characters
• Easy to implement

❌ Cons:

• O(k log k) per word (sorting cost)
• Slower for very long words

When to use

• Default choice for interviews
• Unknown character set
• Words are short (k < 100)

Approach 2: Character Count as Key

The approach

Count characters, use count tuple as key.

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        # Count characters (lowercase English only)
        count = [0] * 26
        for char in word:
            count[ord(char) - ord('a')] += 1
        key = tuple(count)
        groups[key].append(word)
    return list(groups.values())

Complexity

Time: O(n × k) where n = words, k = max word length
Space: O(n × k)

Pros/Cons

✅ Pros:

• O(k) per word (faster than sorting)
• Better for long words

❌ Cons:

• Only works for known alphabet (a-z)
• More code
• Tuple of 26 zeros for each word

When to use

• Optimization when words are long (k > 100)
• Guaranteed lowercase English letters
• Performance matters

Approach 3: Prime Number Product (Rare)

The approach

Assign each letter a prime, multiply them.

from collections import defaultdict

def groupAnagrams(strs):
    # First 26 primes
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
              43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
    
    groups = defaultdict(list)
    for word in strs:
        key = 1
        for char in word:
            key *= primes[ord(char) - ord('a')]
        groups[key].append(word)
    
    return list(groups.values())

Complexity

Time: O(n × k)
Space: O(n × k)

Pros/Cons

✅ Pros:

• O(k) per word
• Compact key (single integer)

❌ Cons:

• Risk of overflow (product can be huge!)
• Only works for small alphabets
• Clever but fragile

When to use

• Almost never in interviews
• Academic interest only
• Don't use unless specifically asked

Comparison

Which to Use in Interviews

Default: Sorted String

key = ''.join(sorted(word))

Why: Simple, works for all cases, easy to explain.

Optimization: Character Count

If interviewer asks "Can you optimize?":

count = [0] * 26
for char in word:
    count[ord(char) - ord('a')] += 1
key = tuple(count)

Why: O(k) instead of O(k log k), shows you know optimization.

Never: Prime Product

Don't use unless specifically asked. Risk of overflow.

Summary

3 approaches for Group Anagrams:

1. Sorted string (default)
2. Character count (optimization)
3. Prime product (avoid)

For interviews: Start with sorted, mention count as optimization if asked.

Next steps:

• Study grouping pattern
• Learn hash map key selection

Choose the right approach for the situation.