Longest valid window expands greedily08.01
For a longest-window problem, advance R whenever you can. Shrink L only when the new R makes the window invalid. Do not shrink a still-valid window to tidy it.
Best length is the maximum R-L+1 among windows that passed the constraint. A shorter valid window inside a longer valid one is not better.
worked examples
Same skill, three traces. Read all three before you try it.
01unique grow - given
s = "abca"- walk
R=0,1,2"abc"unique, keep expandingdo not shrink at
R=2- result
- length
3still valid
02zeros grow - given
a = [1, 0, 0, 1, 9],k=1zeros- walk
[1,0]zeros1, still expandRinvalid only when the second
0enters- result
- greedy expand until zeros>
1
03product grow - given
a = [1, 2, 3, 4], limit10- walk
[1]then[1,2]then[1,2,3]all prod<10stop expanding only after *
4breaks it- result
- longest valid
3
Write
Print every
On
expandGreedy(a).a is an array of integers, or s is a string. R is the right index. Expand R while the window stays valid. The window includes a[L..R].Print every
R where you expand without shrinking. Return nothing.On
"abca" unique, [1, 0, 0, 1, 9] k=1 zeros, and [1, 2, 3, 4] prod<10.constraintsa (or s) is nonempty. Product cases use positive integers. A valid window exists.
- Max Consecutive Ones III0/3 skills ready · sliding window · mediumopen
- Max Consecutive Ones III0/3 skills ready · sliding window · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.