Group Anagrams Using Hash Map in DSA Rust

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 arranging puzzle pieces in the same order, so all puzzles with the same pieces look identical and can be grouped together.

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

hash_map:
  key: sorted letters
  value: list of words

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

Dry Run Walkthrough

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

Goal: Group words that are anagrams together in lists

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

{"aet": ["eat"]}

Why: Sorting letters creates a key that groups anagrams

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

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

Why: Words with same sorted letters belong to same group

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

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

Why: New sorted key creates new group

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

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

Why: Add to existing group with same sorted key

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

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

Why: Add to existing group with same sorted key

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

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

Why: New sorted key creates new group

Result:

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

Annotated Code

DSA Rust

use std::collections::HashMap;

fn group_anagrams(words: Vec<&str>) -> Vec<Vec<String>> {
    let mut map: HashMap<String, Vec<String>> = HashMap::new();
    for word in words {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort_unstable();
        let key: String = chars.into_iter().collect();
        map.entry(key).or_default().push(word.to_string());
    }
    map.into_values().collect()
}

fn main() {
    let input = vec!["eat", "tea", "tan", "ate", "nat", "bat"];
    let grouped = group_anagrams(input);
    for group in grouped {
        println!("{:?}", group);
    }
}

for word in words {

iterate over each word to process

let mut chars: Vec<char> = word.chars().collect();

convert word to list of characters

chars.sort_unstable();

sort characters to create key for anagram group

let key: String = chars.into_iter().collect();

convert sorted characters back to string key

map.entry(key).or_default().push(word.to_string());

add original word to group in hash map under sorted key

map.into_values().collect()

collect all grouped anagrams into a 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 hash map

vs Alternative: Sorting each word is faster than comparing every pair of words which would be O(n^2 * k)

Edge Cases

empty list

returns empty list without error

DSA Rust

for word in words {

list with one word

returns list with one group containing that word

DSA Rust

for word in words {

words with different lengths

groups only words with same sorted letters, different lengths naturally separate

DSA Rust

chars.sort_unstable();

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 group 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 inserting into the hash map

Mistake: Not converting sorted characters back to string key
Fix: Collect sorted chars into a string to use as hash map key

Summary

Groups words that are anagrams by sorting their letters and using the sorted string as a key in a hash map.

Use when you want to find or group all anagrams from a list of words efficiently.

The key insight is that anagrams share the same sorted letter sequence, which can be used as a unique group identifier.

Practice

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

easy

A. Use the length of words as keys to group them

B. Store words in a list without any grouping

C. Group words by their first letter only

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

Solution

1. Step 1: Understand anagram grouping

   Anagrams have the same letters in different orders, so sorting letters gives a common key.

2. Step 2: Use sorted string as hash map key

   By sorting each word and using it as a key, all anagrams map to the same key and group together.

3. Final Answer:

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

4. Quick Check:

   Sorted string key groups anagrams [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Grouping by word length only
• Using first letter as key
• Not sorting letters before grouping

2. Which Rust code snippet correctly creates a hash map to group anagrams by sorted keys?

easy

A. let mut map: HashMap = HashMap::new();

B. let map = Vec::new();

C. let mut map: HashMap = HashMap::new();

D. let mut map: HashMap = HashMap::new();

Solution

1. Step 1: Identify correct hash map type

   We need keys as sorted strings and values as vectors of strings to hold grouped anagrams.

2. Step 2: Match Rust syntax for hash map

   HashMap correctly maps sorted keys to lists of words.

3. Final Answer:

   let mut map: HashMap = HashMap::new(); -> Option A

4. Quick Check:

   HashMap with String keys and Vec<String> values [OK]

Hint: Use HashMap for grouping anagrams [OK]

Common Mistakes:

• Using Vec instead of HashMap
• Wrong value type (String instead of Vec<String>)
• Incorrect key type (i32 instead of String)

3. What is the output of this Rust code that groups anagrams?

use std::collections::HashMap;

fn group_anagrams(words: Vec<&str>) -> Vec {
    let mut map: HashMap = HashMap::new();
    for word in words {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort_unstable();
        let key = chars.into_iter().collect::<String>();
        map.entry(key).or_default().push(word.to_string());
    }
    map.into_values().collect()
}

fn main() {
    let input = vec!["eat", "tea", "tan", "ate", "nat", "bat"];
    let result = group_anagrams(input);
    println!("{:?}", result);
}

medium

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

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

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

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

Solution

1. Step 1: Sort each word to create keys

   "eat", "tea", "ate" all sort to "aet"; "tan", "nat" to "ant"; "bat" to "abt".

2. Step 2: Group words by sorted keys

   Words with same sorted key are grouped: ["eat", "tea", "ate"], ["tan", "nat"], ["bat"].

3. Final Answer:

   [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] -> Option C

4. Quick Check:

   Sorted keys group anagrams [OK]

Hint: Sort letters and group words by sorted key [OK]

Common Mistakes:

• Not sorting letters before grouping
• Grouping single words separately
• Mixing order of groups incorrectly

4. Identify the bug in this Rust code for grouping anagrams:

use std::collections::HashMap;

fn group_anagrams(words: Vec<&str>) -> Vec {
    let mut map: HashMap = HashMap::new();
    for word in words {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort(); // Bug here
        let key = chars.into_iter().collect::<String>();
        map.entry(key).or_default().push(word.to_string());
    }
    map.into_values().collect()
}

medium

A. Use sort_unstable() instead of sort() for better performance

B. Change chars.into_iter() to chars.iter()

C. Use a HashSet instead of HashMap

D. Convert word to lowercase before sorting

Solution

1. Step 1: Identify sorting method issue

   Using chars.sort() works but sort_unstable() is preferred for primitive types like char for speed.

2. Step 2: Explain why sort_unstable() is better

   sort_unstable() is faster and sufficient here because order stability is not needed for grouping anagrams.

3. Final Answer:

   Use sort_unstable() instead of sort() for better performance -> Option A

4. Quick Check:

   sort_unstable() improves sorting speed [OK]

Hint: Use sort_unstable() for sorting chars in anagrams [OK]

Common Mistakes:

• Using sort() unnecessarily slowing code
• Changing iterator type incorrectly
• Ignoring case sensitivity issues

5. Given a list of words with mixed case and spaces, how would you modify the Rust code to group anagrams correctly ignoring case and spaces? Example input: ["Listen", "Silent", "en list", "in lets"]

hard

A. Sort letters without any changes to words

B. Convert words to lowercase and remove spaces before sorting letters

C. Use word length as key for grouping

D. Group words by their first character only

Solution

1. Step 1: Normalize words by removing spaces and converting to lowercase

   To group anagrams ignoring case and spaces, clean words by removing spaces and making all letters lowercase.

2. Step 2: Sort letters of normalized words and use as keys

   After normalization, sort letters to get keys that group all anagrams regardless of case or spaces.

3. Final Answer:

   Convert words to lowercase and remove spaces before sorting letters -> Option B

4. Quick Check:

   Normalize words before sorting for correct grouping [OK]

Hint: Lowercase and remove spaces before sorting letters [OK]

Common Mistakes:

• Not normalizing case and spaces
• Using length or first letter as key
• Sorting original words without cleaning