Shortest valid window shrinks greedily
Updated
For a shortest-window problem, expand until the window is valid, then advance L as far as you can while it stays valid. Record after each successful shrink, not before the first cover.
What to focus on
Leaving extra left cells in a covering window inflates length. Shrink until one more L++ would break the constraint, then expand R again.
Worked examples
cover shrink
s = "ADOBECODEBANC", t = "ABC"- first cover at R=5 len 6
- drop left while missing stays 0 later
- stop shrinking when missing would become 1
Result: min "BANC" length 4
cover abca
s = "abca", t = "ac"- cover "abc" len 3
- after last a, drop b while "ca" still covers
Result: min length 2
sum at least 10
a = [4, 1, 9, 1], need sum ≥ 10- [0,2] sum 14 valid
- drop 4 sum 10 still ≥ 10
- drop 1 sum 9 invalid, put that shrink back
Result: shortest [1,2] length 2
Try it
Write shrinkGreedy(s, t). s is the source string, or a is an array of positive integers. t is the cover requirement, or S is a sum target. L is the left index. After the window is valid, shrink L while it stays valid. Return the shortest valid length. Min cover on ADOBECODEBANC vs ABC and abca vs ac. Then shortest sum ≥ 10 on [4, 1, 9, 1].
s contains a covering of t. All array values are positive integers. S is reachable.