Record the answer when the window is valid
Updated
Update best (length, bounds, or count) only in states that satisfy the constraint. After expand or after shrink, test validity, then maybe write best.
What to focus on
Store L and R when you update, not only the metric. A later invalid window must not overwrite a recorded valid one.
Worked examples
sum ≤ 10
a = [4, 1, 9, 1], need sum ≤ 10- [0,1] sum 5 record len 2
- [1,2] sum 10 record len 2
- [2,3] sum 10 record
Result: recorded [4,1], [1,9], [9,1]
unique
s = "abca"- [0,2] "abc" unique record 3
- [1,3] "bca" unique record 3
Result: best 3 with bounds stored
cover
s = "ADOBECODEBANC", t = "ABC"- record when missing==0
- first at R=5, later BANC beats it
Result: best bounds L=9 R=12
Try it
Write tracer(a). a is an array of integers, or s is a string. L is the left index. R is the right index. The window includes a[L..R]. Record only when the constraint holds. Print RECORD or skip after each move. Return nothing. On [4, 1, 9, 1] sum≤10, "abca" unique, and ADOBECODEBANC vs ABC.
a (or s) is nonempty. All array values are positive. s contains a covering of t.