Extra space of the window state
Updated
Name the state: one integer (sum, prod, zeros, missing) is O(1). A count map is O(distinct) ≤ O(min(n,Σ)). A max-deque of indices is O(n) worst case, O(1) extra besides that.
What to focus on
The window cells themselves are not copied. L and R point into the input. Copying a[L..R] each candidate is O(n) extra work and extra writes, not required for the state.
Worked examples
sum O(1)
a = [4, 1, 9, 1]- state is one number plus L,R
Result: O(1) extra
counts O(Σ)
s = "abcabcbb"- at most 3 keys, or cnt[26]
- n=8
Result: O(1) in alphabet size
deque O(n)
a = [4, 1, 9, 1], decreasing max deque- indices, not a copy of the window
- at most 4 indices live
Result: O(n) worst, still one array
Try it
Write auxSpace(a). a is an array of integers, or s is a string. L and R are indices into the input. State is sum, counts, or a deque, not a copy of a[L..R]. Print extra space in n and Σ for window sum, counts, and a max deque. Return nothing. Sum on [4, 1, 9, 1] is O(1). Counts on "abcabcbb" are O(1) in alphabet size. A max deque is O(n) worst.
a (or s) is nonempty. s uses a bounded alphabet.