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 frequency and when sorted, produce identical strings.

Why HashMap?

  • Allows O(1) grouping of anagrams by their signature
  • Can use sorted string or character count as key
  • Efficient for grouping operations

Approaches:

  1. Sort each string and use as key
  2. Use character frequency array as key (more efficient)

Pattern: "Group by Signature" pattern - using a hash map to group items with common characteristics.

🐍 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 string
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # HashMap to store groups of anagrams
        anagram_map = defaultdict(list)

        for s in strs:
            # Sort the string to create a key
            key = ''.join(sorted(s))
            anagram_map[key].append(s)

        return list(anagram_map.values())

Approach 2: Character Count as Key​

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

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagram_map = defaultdict(list)

        for s in strs:
            # Create character count array as key
            count = [0] * 26  # for 'a' to 'z'
            for char in s:
                count[ord(char) - ord('a')] += 1

            # Convert list to tuple (hashable)
            key = tuple(count)
            anagram_map[key].append(s)

        return list(anagram_map.values())

🔵 Solution: Golang​

Approach 1: Sorted String as Key​

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

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

    for _, s := range strs {
        // Sort the string
        chars := []rune(s)
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        key := string(chars)

        anagramMap[key] = append(anagramMap[key], s)
    }

    result := make([][]string, 0, len(anagramMap))
    for _, group := range anagramMap {
        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 {
    anagramMap := make(map[string][]string)

    for _, s := range strs {
        // Create character count array
        count := make([]int, 26)
        for _, ch := range s {
            count[ch-'a']++
        }

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

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

    return result
}

📚 References​