Group Anagrams Using Hash Map in DSA Go

Mental Model

Group words that have the same letters by sorting their letters and using that as a key.

Analogy: Imagine sorting letters of each word like sorting colored beads in a row; words with the same bead colors in the same order belong together in a box.

words: [eat, tea, tan, ate, nat, bat]

hash map:
key: "aet" -> [eat, tea, ate]
key: "ant" -> [tan, nat]
key: "abt" -> [bat]

Dry Run Walkthrough

Input: words: ["eat", "tea", "tan", "ate", "nat", "bat"]

Goal: Group words that are anagrams into lists together

Step 1: Take word "eat", sort letters to get "aet", add "eat" to map under key "aet"

map: {"aet": ["eat"]}

Why: Sorting letters creates a unique key for all anagrams

Step 2: Take word "tea", sort letters to get "aet", add "tea" to map under key "aet"

map: {"aet": ["eat", "tea"]}

Why: Words with same sorted letters belong in same group

Step 3: Take word "tan", sort letters to get "ant", add "tan" to map under key "ant"

map: {"aet": ["eat", "tea"], "ant": ["tan"]}

Why: New sorted key means new group

Step 4: Take word "ate", sort letters to get "aet", add "ate" to map under key "aet"

map: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

Why: Add to existing group for same sorted key

Step 5: Take word "nat", sort letters to get "ant", add "nat" to map under key "ant"

map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

Why: Add to existing group for same sorted key

Step 6: Take word "bat", sort letters to get "abt", add "bat" to map under key "abt"

map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

Why: New sorted key means new group

Result:

map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}
Groups: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

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

	for _, word := range strs {
		chars := []rune(word)
		sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
		sortedWord := string(chars)

		anagramMap[sortedWord] = append(anagramMap[sortedWord], word)
	}

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

	return result
}

func main() {
	words := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	groups := groupAnagrams(words)
	for _, group := range groups {
		fmt.Println(group)
	}
}

for _, word := range strs {

iterate over each word to process

chars := []rune(word)

convert word to slice of characters for sorting

sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })

sort characters to get canonical form

sortedWord := string(chars)

convert sorted characters back to string key

anagramMap[sortedWord] = append(anagramMap[sortedWord], word)

add original word to group keyed by sorted letters

for _, group := range anagramMap {

collect all groups from map into result list

Output

[eat tea ate]

[tan nat]

[bat]

Complexity Analysis

Time: O(n * k log k) because we sort each of the n words of length k

Space: O(n * k) because we store all words and keys in the map

vs Alternative: Sorting each word is faster and simpler than checking all pairs for anagram equality which would be O(n^2 * k)

Edge Cases

empty input list

returns empty list with no groups

DSA Go

for _, word := range strs {

single word input

returns one group containing that word

DSA Go

for _, word := range strs {

words with duplicates

duplicates appear together in the same group

DSA Go

anagramMap[sortedWord] = append(anagramMap[sortedWord], word)

When to Use This Pattern

When you need to group words that are made of the same letters, use sorting as a key in a hash map to collect anagrams efficiently.

Common Mistakes

Mistake: Using the original word as key instead of sorted letters
Fix: Sort the letters of the word first to create the key before grouping

Mistake: Not converting sorted characters back to string before using as map key
Fix: Convert the sorted rune slice back to string to use as map key

Summary

Groups words that have the same letters into lists using a hash map keyed by sorted letters.

Use when you want to find all anagrams grouped together from a list of words.

The key insight is that sorting letters of anagrams produces the same string, which can be used as a unique group key.

Practice

1. What is the main idea behind grouping anagrams using a hash map?

easy

A. Use the last letter of each word as the key

B. Use the length of words as keys to group anagrams

C. Use sorted strings as keys to group words with the same letters

D. Use the first letter of each word as the key

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted string as key

   Sorting letters of each word gives a unique key for all its anagrams.

3. Final Answer:

   Use sorted strings as keys to group words with the same letters -> Option C

4. Quick Check:

   Sorted string key = group anagrams [OK]

Hint: Sort letters to find anagram groups quickly [OK]

Common Mistakes:

• Using word length as key misses different anagrams
• Using first or last letter groups unrelated words
• Not sorting letters before using as key

2. Which Go code snippet correctly initializes a hash map to group anagrams?

easy

A. groups := make(map[string][]string)

B. groups := map[string]string{}

C. groups := make([]string, 0)

D. groups := map[int][]string{}

Solution

1. Step 1: Identify map key and value types

   Key should be string (sorted word), value should be slice of strings (anagrams).

2. Step 2: Check Go map initialization syntax

   make(map[string][]string) creates a map with string keys and string slice values.

3. Final Answer:

   groups := make(map[string][]string) -> Option A

4. Quick Check:

   Correct map type and initialization [OK]

Hint: Use map[string][]string for grouping anagrams [OK]

Common Mistakes:

• Using map[string]string instead of map[string][]string
• Using slice instead of map
• Using wrong key or value types

3. What is the output of the following Go code?

package main
import (
  "fmt"
  "sort"
  "strings"
)
func groupAnagrams(strs []string) map[string][]string {
  groups := make(map[string][]string)
  for _, word := range strs {
    letters := strings.Split(word, "")
    sort.Strings(letters)
    key := strings.Join(letters, "")
    groups[key] = append(groups[key], word)
  }
  return groups
}
func main() {
  input := []string{"bat", "tab", "eat", "tea"}
  result := groupAnagrams(input)
  fmt.Println(result)
}

medium

A. map[bat:[bat] tab:[tab] eat:[eat] tea:[tea]]

B. map[abt:[bat] tab:[tab] aet:[eat] tea:[tea]]

C. map[bat:[bat tab] eat:[eat tea]]

D. map[abt:[bat tab] aet:[eat tea]]

Solution

1. Step 1: Sort letters of each word

   "bat" and "tab" sorted to "abt"; "eat" and "tea" sorted to "aet".

2. Step 2: Group words by sorted key

   Words with key "abt" grouped as ["bat", "tab"], with key "aet" grouped as ["eat", "tea"].

3. Final Answer:

   map[abt:[bat tab] aet:[eat tea]] -> Option D

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

Hint: Sorted keys map to anagram groups [OK]

Common Mistakes:

• Not sorting letters before grouping
• Using original words as keys
• Incorrect map output format

4. Find the error in this Go code for grouping anagrams:

func groupAnagrams(strs []string) map[string][]string {
  groups := make(map[string][]string)
  for _, word := range strs {
    letters := strings.Split(word, "")
    sort.Strings(letters)
    key := letters[0]
    groups[key] = append(groups[key], word)
  }
  return groups
}

medium

A. Appending word to wrong map key

B. Using letters[0] as key instead of full sorted string

C. Not initializing the map before use

D. Missing import for strings package

Solution

1. Step 1: Check key creation logic

   Key is set as letters[0], only first letter of sorted word, not full sorted string.

2. Step 2: Understand impact on grouping

   Using only first letter groups unrelated words, failing to group anagrams correctly.

3. Final Answer:

   Using letters[0] as key instead of full sorted string -> Option B

4. Quick Check:

   Full sorted string needed as key [OK]

Hint: Use full sorted string as key, not just first letter [OK]

Common Mistakes:

• Using partial key instead of full sorted string
• Forgetting to join letters into string key
• Not sorting letters before key creation

5. Given the input list ["listen", "silent", "enlist", "google", "gogole", "abc"], which Go code snippet correctly returns the grouped anagrams as a slice of slices of strings (ignoring order)?

hard

A. func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, word := range strs {
letters := strings.Split(word, "")
sort.Strings(letters)
key := strings.Join(letters, "")
groups[key] = append(groups[key], word)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}

B. func groupAnagrams(strs []string) [][]string {
groups := make(map[int][]string)
for _, word := range strs {
key := len(word)
groups[key] = append(groups[key], word)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}

C. func groupAnagrams(strs []string) [][]string {
groups := make(map[string]string)
for _, word := range strs {
letters := strings.Split(word, "")
sort.Strings(letters)
key := strings.Join(letters, "")
groups[key] = word
}
result := [][]string{}
for _, group := range groups {
result = append(result, []string{group})
}
return result
}

D. func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, word := range strs {
key := word
groups[key] = append(groups[key], word)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}

Solution

1. Step 1: Use sorted string as key and map to slice of strings

   func groupAnagrams(strs []string) [][]string { groups := make(map[string][]string) for _, word := range strs { letters := strings.Split(word, "") sort.Strings(letters) key := strings.Join(letters, "") groups[key] = append(groups[key], word) } result := [][]string{} for _, group := range groups { result = append(result, group) } return result } correctly sorts letters, joins them as key, and appends words to groups[key].

2. Step 2: Convert map values to slice of slices

   func groupAnagrams(strs []string) [][]string { groups := make(map[string][]string) for _, word := range strs { letters := strings.Split(word, "") sort.Strings(letters) key := strings.Join(letters, "") groups[key] = append(groups[key], word) } result := [][]string{} for _, group := range groups { result = append(result, group) } return result } collects all groups into a slice of slices and returns it.

3. Final Answer:

   Option A code correctly groups anagrams and returns slice of slices -> Option A

4. Quick Check:

   Sorted key + map to slices + collect groups = correct [OK]

Hint: Sort letters, map to slices, then collect groups [OK]

Common Mistakes:

• Using word length as key groups wrong words
• Using map[string]string loses multiple anagrams per key
• Using original word as key misses grouping