49. Group Anagrams

Array
Hash Table
String
Sorting

TIME

O(n × k)

SPACE

O(n × k)

Intuition

Anagrams have the same character frequency. Use character count as a key to group strings together.

Solution

Character count as key: For each string, compute a frequency array of 26 integers (one per letter).
Convert to hashable key: Convert the frequency array to a tuple (Python) or string (Java) to use as a hash map key.
Group by key: Strings with the same key are anagrams, append them to the same list.
Return all groups: Return all values from the hash map.

Why Character Count over Sorting?

Sorting each string: O(k log k) per string
Character count: O(k) per string
For long strings, counting is faster

Complexity

Time: O(n × k) where n = number of strings, k = max string length
Space: O(n × k), storing all strings in the hash map

Edge Cases

Empty string "" → valid anagram group of its own
Single character strings
All strings are anagrams → single group
No anagrams → each string is its own group

Code

from typing import List
from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        49. Group Anagrams
        Time: O(n × k)
        Space: O(n × k)
        """
        groups = defaultdict(list)
        
        for s in strs:
            count = [0] * 26
            for ch in s:
                count[ord(ch) - 97] += 1
            groups[tuple(count)].append(s)
        
        return list(groups.values())

import java.util.*;

/**
 * 49. Group Anagrams
 * Time: O(n × k)
 * Space: O(n × k)
 */
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String s : strs) {
            int[] count = new int[26];
            for (char ch : s.toCharArray()) {
                count[ch - 'a']++;
            }
            
            String key = Arrays.toString(count);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(groups.values());
    }
}