Skip to content

← Collections, Text and First Iterators step 15 of 21

Medium Primitives

Group anagrams with a map

Group words that contain the same Unicode scalar values with the same counts.

pub fn anagram_groups(words: Vec<String>) -> Vec<Vec<String>>

Keep every input word, including duplicates and empty strings. Preserve input order within each group. Sort the groups by:

  1. Size, largest first.
  2. The group's first word, ascending, when sizes are equal. Use Rust's ordinary string ordering, not a locale-specific dictionary order.

For example, ["dog", "cat", "god", "act"] produces [["cat", "act"], ["dog", "god"]]. Both groups contain two words, so their first words determine the order. An empty input produces an empty result.

Comparison is case-sensitive: "Ab" and "ab" belong to different groups. Use chars() to work with Unicode scalar values. "éa" and "aé" belong together, but the single scalar "é" and the two-scalar string "e\u{301}" do not. This exercise does not normalize text or group by displayed graphemes.

Give matching words the same key

Sort each word's characters to build its key. For example, "eat", "tea", and "ate" all produce "aet". A map can then associate each key with a vector of the original words.

This small example shows the entry operation without the anagram-key step:

use std::collections::BTreeMap;

fn main() {
    let mut groups: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
    for (key, word) in [("aet", "eat"), ("ant", "tan"), ("aet", "tea")] {
        groups.entry(key).or_default().push(word);
    }
    assert_eq!(groups["aet"], ["eat", "tea"]);
}

entry locates a key's entry. or_default() inserts an empty vector if the key is absent, then returns a mutable reference to the vector. Appending words as you encounter them preserves their input order.

A BTreeMap iterates in key order, but that is not the required result order. You still need to sort the completed groups by size and first word. A HashMap can also work with that final sort. Use the standard library for this exercise.

Move each word into its group

The starter fails with E0507 at push(*w). Its loop, for w in &words, gives you a borrowed &String, while each output group needs owned String values. Dereferencing does not let you take a non-Copy value through a shared reference.

The function already owns words, so iterate over words by value. Each iteration then gives you an owned string to move into its group. Moving avoids copying the string's text buffer. Building character keys, map entries, and output vectors still requires storage.

Cloning each borrowed string would also provide an owned value, but adds copying that this signature does not require. A borrowed-result API would need borrowed input that outlives the returned references; it cannot return references into a local input vector that is about to be dropped. Even Vec<Vec<&str>> still needs storage for the vectors, though the references can reuse the original text.

Check your understanding Could the map key be a sorted Vec<char> instead of a String? Show answer

Yes. Both types support ordering and can represent the sorted sequence of scalar values.

A char occupies four bytes. A String stores UTF-8 text, using one to four bytes per scalar value, plus its buffer metadata and any spare capacity. It is not a fixed four-byte key. Choose a representation that fits the operations you need; either works for this exercise.

Sorting bytes instead does not preserve the exercise's character-count rule. It can also produce bytes that cannot be converted into a valid UTF-8 string. Use chars() when building the key.

Adjacent chunks are different from global groups

slice::chunk_by returns slices of consecutive elements whose neighboring pairs satisfy a predicate:

fn main() {
    let values = [1, 1, 2, 2, 1];
    let mut chunks = values.chunk_by(|left, right| left == right);
    assert_eq!(chunks.next(), Some(&[1, 1][..]));
    assert_eq!(chunks.next(), Some(&[2, 2][..]));
    assert_eq!(chunks.next(), Some(&[1][..]));
    assert_eq!(chunks.next(), None);
}

The final 1 forms a separate chunk. Anagram groups must combine matching words even when other words occur between them.

Sorting by anagram key before chunking is another possible approach. A stable sort would preserve input order among equal keys; you would still need to construct the owned output and sort its groups. Neither approach is universally faster. The map approach directly collects words as they arrive.

Sort the completed groups

The starter's intermediate value contains (key, words) pairs. Its comparator is:

// Fragment: groups is a Vec<(String, Vec<String>)> of nonempty groups.
groups.sort_by(|a, b| {
    b.1.len().cmp(&a.1.len())
        .then_with(|| a.1[0].cmp(&b.1[0]))
});

Swapping the operands makes the size comparison descending. then_with compares the first words only when the sizes match. Index 0 is valid because a map entry is created when its first word is appended; there are no empty groups.

You can name the intermediate type with type Grouped = Vec<(String, Vec<String>)>; if that makes the code easier to read. Keep the given function signature. Submissions must compile, pass the test cases, and pass the configured Clippy checks.

Further reading: String representation, str::chars, and slice::chunk_by.