Why it works
- An answer is n words in a row, so the window is a fixed n · L letters and moves a whole word at a time: one word comes in, one leaves, and seen is updated in O(1).
- Moving by a word only visits starts offset, offset + L, …, so the passes from 0 to L - 1 together try every start. Here "tobe" at 1 is seen only by the pass from 1.
- The window holds exactly n words, so if every word has its count from need, nothing else fits in: the window is the words in some order.
Complexity
Time O(|s| · (L + n)): the L passes together take about |s| steps, and each step cuts a word of L letters and checks need, which holds at most n words. Memory O(n · L + |s|): need holds the words, and seen keeps every word met in a pass, at 0 once it has left.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗