709. Where All the Words Sit Together

You are given a string s and m words, ALL OF THE SAME LENGTH L. Print every starting position in s at which the next m * L characters are a concatenation of all m words, each used exactly once, in any order.

Repeated words in the list must be matched the right number of times.

Print the positions in increasing order on one line, or none if there are none.

s = barfoothefoobarman, words = foo bar -> 0 9 s = barfoofoobarthefoobarman, words = bar foo the -> 6 9 12 s = wordgoodgoodgoodbestword, words = word good best word -> none

## The words are all the same length, and that changes everything

Because every word has length L, any valid block splits at positions that are all congruent modulo L. So a start at position 5 and a start at position 5 + L share their whole decomposition, while a start at 5 and a start at 6 share nothing.

That splits the string into L independent tracks. Within one track, the string is a sequence of L-sized chunks and the question becomes the familiar one: which windows of m consecutive chunks match the required multiset.

Turning a character problem into L separate chunk problems is the whole idea.

## One sweep per track

For each offset 0 .. L-1, walk the chunks left to right holding a tally of the chunks in the current window.

· chunk not in the required list: clear the window and restart after it · chunk present but now too frequent: drop chunks from the left until it is not · window holds m chunks: record its start, then drop one from the left and continue

Dropping exactly one after a hit is what finds overlapping answers. On aaa with words a a, positions 0 and 1 both qualify, and restarting instead of stepping misses the second.

## Why this is linear

Each chunk is entered once and left once per track, and there are n / L chunks per track across L tracks, so O(n) chunk operations in all, each costing O(L) to hash. The total is O(n L), against O(n m L) for testing every start independently.

## Boundaries

m * L longer than s gives none. A word list of one word reduces to plain substring search.

## Cost

Time O(n L). Space O(m L) for the tallies.

Constraints - `1 ≤ length of s ≤ 10000` - `1 ≤ m ≤ 100` - `1 ≤ L ≤ 10` - all characters are lowercase letters