NUHMAN.com

Introduction

LeetCode 49: Group Anagrams is a popular string-based problem that challenges you to group together words that are anagrams of each other. An anagram is a word formed by rearranging the letters of another word. For example, "listen" and "silent" are anagrams.

This is an ideal problem to solve using a hash map and sorted strings as keys, and is frequently asked in coding interviews at top tech companies.

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

go

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

Example 2:

go

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

Example 3:

go

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

Approach: Hash Map + Sorted Key

To determine if two strings are anagrams:

• Sort the characters in both strings.
• If they are equal, they are anagrams.

We'll use this idea to group strings:

1. Sort each string.
2. Use the sorted string as a key in a map.
3. Append the original string to the list corresponding to that key.

Go Implementation

go

import (
    "sort"
    "strings"
)

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

    for _, str := range strs {
        sortedStr := sortString(str)
        anagramMap[sortedStr] = append(anagramMap[sortedStr], str)
    }

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

    return result
}

// Helper function to sort a string alphabetically
func sortString(s string) string {
    chars := strings.Split(s, "")
    sort.Strings(chars)
    return strings.Join(chars, "")
}

Example Walkthrough

Input:

go

strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}

Sorted Map Keys:

• "eat", "tea", "ate" → sorted as "aet" → group: ["eat", "tea", "ate"]
• "tan", "nat" → sorted as "ant" → group: ["tan", "nat"]
• "bat" → "abt" → group: ["bat"]

Final Output:

go

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

Time and Space Complexity

MetricComplexityTime ComplexityO(n·k log k)Space ComplexityO(n·k)

• n: number of strings
• k: maximum length of a string
• Time Complexity: For each of the n strings, we sort it (O(k log k)), and insert into the map.
• Space Complexity: Storing the grouped strings takes O(n·k) space in the worst case.

Alternative Approach (Count Frequency Key)

Instead of sorting, you can build a character frequency array of size 26 (for lowercase English letters) as the map key. This improves performance for very long strings.

Edge Cases

• Empty string: Should be grouped with other empty strings.
• Single-character strings: Group separately unless they are the same character.
• Large dataset: Map ensures efficiency even with many strings.

Key Takeaways

• Sorting + HashMap is a clean and simple method to group anagrams.
• Consider frequency-count-based keys for improved performance.
• Mastering map-based grouping is a key skill in Go and other languages for solving string problems efficiently.