Group Anagrams Using Hash Map in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an anagram?

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all original letters exactly once.

beginner

Why do we use a hash map to group anagrams?

A hash map helps group anagrams by using a key that represents the sorted letters of each word. Words with the same sorted key are anagrams and stored together.

beginner

How do you create a key for each word to group anagrams?

Sort the letters of the word alphabetically and use the sorted string as the key in the hash map.

intermediate

What is the time complexity of grouping anagrams using a hash map?

The time complexity is O(N * K log K), where N is the number of words and K is the maximum length of a word (due to sorting each word).

beginner

What data structure is used to store groups of anagrams in the hash map?

A list (or slice in Go) is used as the value in the hash map to store all words that share the same sorted key.

What is the key used in the hash map to group anagrams?

A The first letter of the word

B The length of the word

C The sorted string of the word's letters

D The original word itself

The sorted string of the word's letters is used as the key because all anagrams share the same sorted letters.

Which data structure is best to store groups of anagrams?

A Stack

B Hash map with list values

C Queue

D Binary tree

A hash map with lists as values allows grouping words by their sorted keys efficiently.

What is the main operation done on each word before using it as a key?

A Reversing the word

B Counting vowels

C Converting to uppercase

D Sorting its letters alphabetically

Sorting letters alphabetically creates a uniform key for all anagrams.

If two words have the same sorted key, what does it mean?

A They are anagrams

B They have the same length

C They start with the same letter

D They are identical

Same sorted key means the words have the same letters in the same frequency, so they are anagrams.

What is the main cost in time complexity when grouping anagrams?

A Sorting each word

B Inserting into the hash map

C Comparing words

D Counting characters

Sorting each word takes O(K log K) time, which dominates the overall complexity.

Explain how to group a list of words into anagrams using a hash map.

Think about how sorting helps identify anagrams.

Describe the role of the hash map in the anagram grouping problem.

Focus on how keys and values relate.

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