Recognize an amortized linear window scan
Updated
A while-shrink nested inside for-R looks O(n²). It is O(n) when L and R each move at most n times: every inner step permanently advances L.
What to focus on
Charge each include to R++ and each exclude to L++. Total body executions ≤ 2n. If L ever decreases, the charge fails and you no longer have this scan.
Worked examples
count moves
a = [4, 1, 9, 1], sum ≤ 10- R++ four times
- L++ at R=2 (drop 4) and maybe later
- ≤ 8 pointer moves
Result: O(n) not O(n²)
unique shrinks
s = "abcabcbb"- R++ eight times
- several L++ but each index left at most once
Result: ≤ 16 moves, O(n)
nested trap
s = "abca", restart R from L each L- for L, R walks to n
- enters repeat
Result: O(n²), not amortized linear
Try it
Write countMoves(a). a is an array of integers, or s is a string. L and R each move at most n times if every inner shrink permanently advances L. Print R++ and L++ counts. Return nothing. On [4, 1, 9, 1] sum≤10 and "abcabcbb" unique. Then a restart-R nested loop on "abca".
a (or s) is nonempty. All array values are positive.