Skip to main content

🟨 Group Anagrams (#49)

🔗 Problem Link​

📋 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 or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

💡 Examples​

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"]]

🔑 Key Insights & Approach​

Core Observation: Anagrams have the same character counts. If we can create a unique identifier for each group of anagrams, we can use a hash map to group them together.

Why Hash Map?

  • Group by pattern: Map unique identifiers to lists of words
  • O(1) lookup: Check if we've seen this anagram pattern before
  • Single pass: Process each word once

Two Key Implementation Choices:

  1. Sorted string as key: "eat" → "aet" - Sort each word and use it as the hash key

    • Time: O(n * k log k) where k is max word length
    • Simple and intuitive

  2. Character count as key: "eat" → (1,0,0,0,1,0...1,0) - Count frequency of each letter

    • Time: O(n * k) where k is max word length
    • Faster but slightly more complex

Why Approach 2 is Better:

  • Avoids sorting overhead: O(k) instead of O(k log k) per word
  • Still provides unique identifier for anagram groups

Pattern Recognition: This is the "Categorize by Key" pattern - when you need to group items that share a property, use a hash map with a unique identifier as the key.

🐍 Solution: Python​

Approach 1: Sorted String as Key​

Time Complexity: O(n * k log k) | Space Complexity: O(n * k)

  • n = number of strings, k = maximum length of a string
from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    anagrams = defaultdict(list)

    for s in strs:
        # Sort the string and use it as key
        key = ''.join(sorted(s))
        anagrams[key].append(s)

    return list(anagrams.values())

Approach 2: Character Count as Key (Optimal)​

Time Complexity: O(n * k) | Space Complexity: O(n * k)

from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    anagrams = defaultdict(list)

    for s in strs:
        # Count characters (26 letters)
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1

        # Use tuple of counts as key (lists aren't hashable)
        key = tuple(count)
        anagrams[key].append(s)

    return list(anagrams.values())

🔵 Solution: Golang​

Approach 1: Sorted String as Key​

Time Complexity: O(n * k log k) | Space Complexity: O(n * k)

import (
    "sort"
    "strings"
)

func groupAnagrams(strs []string) [][]string {
    anagrams := make(map[string][]string)

    for _, s := range strs {
        // Sort the string and use as key
        chars := strings.Split(s, "")
        sort.Strings(chars)
        key := strings.Join(chars, "")
        anagrams[key] = append(anagrams[key], s)
    }

    result := make([][]string, 0, len(anagrams))
    for _, group := range anagrams {
        result = append(result, group)
    }

    return result
}

Approach 2: Character Count as Key​

Time Complexity: O(n * k) | Space Complexity: O(n * k)

import "fmt"

func groupAnagrams(strs []string) [][]string {
    anagrams := make(map[string][]string)

    for _, s := range strs {
        // Count characters
        count := [26]int{}
        for _, c := range s {
            count[c - 'a']++
        }

        // Convert count array to string key
        key := fmt.Sprintf("%v", count)
        anagrams[key] = append(anagrams[key], s)
    }

    result := make([][]string, 0, len(anagrams))
    for _, group := range anagrams {
        result = append(result, group)
    }

    return result
}

📚 References​