Grouping without itertools: anagram buckets

Group words that are anagrams of each other.

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

Two words belong together when they are permutations of the same multiset of characters. Ordering of the result:

• groups sorted by size descending;
• ties broken by the group’s first word ascending;
• words within a group stay in input order.

Comparison is exact — "Ab" and "ab" are not anagrams, because 'A' and 'a' are different characters. Non-ASCII words work the same way: characters, not bytes.

There is no group_by in std

In most ecosystems this is one call: itertools.groupby, Enumerable#group_by, _.groupBy, stream().collect(groupingBy(..)). Rust’s standard library has none of them, and this site has no external crates at all — so if your first move is to reach for itertools::Itertools::into_group_map, you are about to hit a wall.

That is a feature here rather than a hardship. The std answer is four lines and once you have written it you will never be confused about what into_group_map does:

let mut map: BTreeMap<Key, Vec<Item>> = BTreeMap::new();
for item in items {
    map.entry(key_of(&item)).or_default().push(item);
}

A map from key to Vec — a multimap — plus the Entry API from earlier in this track. or_default() creates the empty Vec on first sight of a key and hands you a &mut Vec either way, so there is exactly one lookup per item.

Use a BTreeMap rather than a HashMap and the buckets come out in key order, which makes the whole function deterministic before you even start sorting.

chunk_by is a different operation, and people conflate them

Rust does have a grouping primitive: slice::chunk_by. It groups adjacent elements that satisfy a predicate:

[1, 1, 2, 2, 1].chunk_by(|a, b| a == b)   // [1,1], [2,2], [1]

Note the trailing [1]: it is a third group, not part of the first. That is the whole difference. chunk_by needs no map and no allocation because it only ever compares neighbours; grouping by an arbitrary key needs a map, because the matching item may be anywhere.

A useful equivalence: sort by the key first and chunk_by becomes interchangeable with the map version — at the cost of an O(n log n) sort. If the data is already sorted, chunk_by is strictly better. If it is not, the map is.

The compile error

error[E0507]: cannot move out of `*w` which is behind a shared reference

The starter iterates for w in &words, so w is a &String — borrowed. Pushing into a Vec<String> needs an owned String, and *w does not conjure ownership; dereferencing a shared reference gives you a place you may read, not a value you may take. Rust is refusing to leave a hole in words.

Three ways out, and choosing between them is the actual lesson:

1. for w in words — consume the vector. You own each String, no clone, no allocation. Correct here, because the caller gave you the Vec by value and does not want it back.
2. w.clone() — keep words intact and pay for a copy per word. Correct if you need the input afterwards.
3. change the return type to Vec<Vec<&str>> — hand back borrowed slices and allocate nothing at all. Correct if the caller keeps words alive.

The signature already decided for you: words: Vec<String> by value means the caller handed over ownership, so option 1 is free and the other two are paying for something nobody asked for.

::: question Why is the key a String of sorted characters rather than a sorted Vec<char>? Either works — Vec<char> is Ord, so a BTreeMap<Vec<char>, _> compiles and behaves identically. String is chosen because it is four bytes per key rather than four bytes per character plus a pointer, and because it is what you would want if the key ever needed printing or storing.

What does not work is sorting the bytes: w.as_bytes().sort() would scramble multi-byte UTF-8 sequences and could produce a key that is not valid UTF-8 at all. chars() iterates whole scalar values, which is why the non-ASCII test case passes. (Strictly, even chars() is not the last word — a combining accent is two chars that render as one grapheme — but that needs a crate, and for this problem characters are the right unit.) :::

Sorting the groups

Two keys, one descending and one ascending, so a single sort_by with a chained comparator:

groups.sort_by(|a, b| b.1.len().cmp(&a.1.len())     // size, descending
                       .then_with(|| a.1[0].cmp(&b.1[0])));  // first word, ascending

Descending is expressed by swapping the operands, not by negating anything. then_with runs its closure only when the first comparison was Equal.

One style note. Vec<(String, Vec<String>)> as an intermediate type is readable but noisy, and a type alias costs one line:

type Grouped = Vec<(String, Vec<String>)>;

clippy has a type_complexity lint for genuinely unreadable types — verified against clippy 0.1.95, its default threshold does not fire on a two-level type like this one, but it does on a three-level nest such as BTreeMap<String, Vec<(String, Vec<Option<String>>)>>. When it does fire, the fix is the alias, not an #[allow].

Remember the grade is compile + tests + clippy -D warnings.