Group Anagrams Using Hash Map in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of grouping anagrams?

Given the Rust code below that groups anagrams from a list of words, what is the printed output?

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 = 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 groups = group_anagrams(input);
    println!("{:?}", groups);
}

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

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

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

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

💡 Hint

Rust's HashMap preserves insertion order of keys since Rust 1.56, so groups appear in order of first insertion of each key.

The code groups words by their sorted character key. Words with the same sorted characters are grouped together. The order of groups follows HashMap insertion order ('aet', 'ant', 'abt'). Option D shows this valid grouping.

🧠 Conceptual

intermediate

Why use sorted strings as keys in grouping anagrams?

In the context of grouping anagrams using a hash map, why do we use the sorted version of each word as the key?

A Because the original words cannot be used as keys in a hash map.

B Because sorting strings improves the performance of hash map lookups.

C Because sorted strings are unique identifiers for anagram groups, ensuring all anagrams share the same key.

D Because sorting removes duplicate characters from the words.

💡 Hint

Think about what makes anagrams similar and how to represent that similarity as a key.

Sorting the characters of a word produces a canonical form that is identical for all anagrams. This allows grouping all anagrams under the same key in the hash map.

🔧 Debug

advanced

Identify the runtime error in this anagram grouping code

What runtime error will this Rust code produce when grouping anagrams, and why? ```rust use std::collections::HashMap; fn group_anagrams(words: Vec<&str>) -> Vec> { let mut map: HashMap> = HashMap::new(); for word in words { let key = word.to_string(); let mut chars: Vec = key.chars().collect(); chars.sort_unstable(); map.entry(key).or_default().push(word.to_string()); } map.into_values().collect() } ```

A No runtime error; code runs correctly and groups anagrams.

B Logic error: groups will not be formed correctly because keys are not sorted strings.

C Panic due to borrowing `key` after it is moved into the hash map entry.

D Compilation error due to mutable and immutable borrow conflict.

💡 Hint

Check how the key is created and used for grouping.

The key used in the hash map is the original word string, not the sorted string. This means anagrams have different keys and won't be grouped together, causing a logic error but no runtime panic.

📝 Syntax

advanced

Which option fixes the syntax error in this Rust anagram grouping snippet?

The following Rust code snippet has a syntax error. Which option fixes it? ```rust let mut map: HashMap> = HashMap::new() for word in words { let mut chars = word.chars().collect::>(); chars.sort_unstable(); let key = chars.into_iter().collect::(); map.entry(key).or_default().push(word.to_string()); } ```

A Add a semicolon after HashMap::new(): `HashMap::new();`

B Replace `collect::<Vec<char>>()` with `collect<Vec<char>>()`

C Change `or_default()` to `or_insert()`

D Add `mut` before `word` in the for loop: `for mut word in words`

💡 Hint

Look carefully at the line endings and Rust syntax rules.

The missing semicolon after `HashMap::new()` causes a syntax error. Adding it fixes the error. Other options do not fix the syntax error.

🚀 Application

expert

How many groups are formed by this anagram grouping code?

Given the input list `["listen", "silent", "enlist", "google", "gogole", "abc", "cab", "bac", "foo"]`, how many groups will the Rust anagram grouping code produce?

A 4

B 3

C 5

D 6

💡 Hint

Group words by their sorted characters and count unique groups.

The groups are: ["listen", "silent", "enlist"], ["google", "gogole"], ["abc", "cab", "bac"], and ["foo"]. Total 4 groups.

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