Prove a discarded prefix cannot return
Updated
L never decreases. Once index i is dropped, it is outside every later window. Future R only grows, so a window that put i back would be [i, R'] with R' ≥ current R.
What to focus on
For longest-invalid-then-shrink: [L-1, R] was already invalid, so [L-1, R'] with more of the right stays invalid (or no better). For shortest-cover, extras on the left were optional. You already tested that dropping them kept cover.
Worked examples
sum drop 4
a = [4, 1, 9, 1], sum ≤ 10, drop index 0 at R=2- [0,2] sum 14 invalid
- any R'≥2 still includes 4+1+9 plus more
- later [1,2] and [2,3] do not need 4
Result: index 0 never returns
unique drop a
s = "abca", drop index 0 at R=3- s[0] and s[3] are both a
- keeping 0 with R=3 is the duplicate
- L=1..3 is the only unique option
Result: index 0 never returns
zeros drop into second 0
a = [1, 0, 0, 1, 9], k=1, L moves to 2- windows that keep index 0 or 1 with R≥2 have two zeros
- later [2,4] zeros 1
Result: indices 0 and 1 stay discarded
Try it
Write whyDropped(a, L). a is an array of integers, or s is a string. L is the left index that just advanced. L never decreases. The dropped index is outside every later window. After each shrink, print why the old L cannot come back. Return nothing. On [4, 1, 9, 1] sum≤10, "abca" unique, and [1, 0, 0, 1, 9] k=1.
a (or s) is nonempty. All array values are positive. L only increases.