Build a byte index with one allocation

Build a byte-offset index while avoiding repeated growth of the output vector. The starter returns the right offsets, but exceeds the allocation budget on larger inputs.

What to return

Implement build_index(words: Vec<String>) -> Vec<u32>.

Return words.len() + 1 offsets. The first is zero; offset i is the sum of the byte lengths of the first i words. Preserve input order and include an offset for every word, including empty strings.

["ab", "abab"] -> [0, 2, 6]
["é", "", "猫"] -> [0, 2, 2, 5]
[] -> [0]

String::len() counts UTF-8 bytes, so "é" contributes two bytes and "猫" contributes three. Assume the total byte length fits in u32 and the output vector fits in memory.

These offsets could locate each word in a separate buffer containing all the words concatenated without separators. This function only builds the offsets; it does not create that buffer.

What the allocation check measures

The harness constructs the input before resetting an allocation counter. During build_index, it counts calls to the global allocator's alloc, alloc_zeroed and realloc methods. Their combined count must be at most one. Deallocating the input does not increase it, and formatting the output happens after the count is read.

Harness input n generates n words by repeating "ab" one through five times in a cycle. The output reports the index length, its first six entries (or fewer), its final offset and alloc_ok. The largest seeded case uses 200,000 words and requires 200,001 offsets.

This checks allocation calls in the exercise's build and harness, not a time limit or the number of bytes copied. Allocator counters are diagnostic measurements, not a language-level guarantee that every allocation expression produces an observable call.

Reserve space before pushing

The final number of offsets is known before the loop. Reserving enough capacity once lets you append them without growing the output buffer. Remember to include space for the leading zero.

Capacity is space available for elements; length is the number already initialized. Reserving capacity alone does not add the zero or any offsets.

Starting with Vec::new() allocates no buffer. Pushing beyond capacity causes growth. Rust does not guarantee a particular growth factor, and a reallocation may grow a buffer in place rather than copying it. Avoid predicting an exact allocation or copy count from a doubling model.

An iterator collected into a vector may also reserve enough space up front. Its allocation behavior depends on the iterator and collection implementation; an exact size hint is not a general one-allocation guarantee. Check alternatives against this harness.

Applying this outside the exercise

Reserving a known size can reduce growth even for a small collection. Whether the difference matters depends on the workload. Here the explicit allocation budget makes that choice part of the exercise.

Calling shrink_to_fit afterward can make another allocator call, so it can break this budget. In other code, weigh the retained spare capacity against the cost of shrinking.

An empty Vec still has a pointer, length and capacity, even when it owns no heap buffer. Those fields are not necessarily stored on the stack. Option<Vec<T>> can be useful when “not supplied” and “supplied but empty” mean different things; allocation avoidance alone does not decide that API.

The submission must also compile, match the expected output and pass Clippy with warnings denied.