Grow a contiguous interval and repair it
A sliding window maintains information about a contiguous interval while moving its boundaries. We study two different tasks: the shortest interval reaching a positive sum target in a nonnegative array, and the longest substring containing at most k distinct characters. Both update state for entering and leaving elements instead of rebuilding the interval summary from scratch.
Their repair conditions and answer-update timing are different. For the shortest sum interval, record a length while the target is satisfied and then shrink. For the longest distinct-character interval, shrink while the constraint is broken and only record the repaired interval. The name sliding window does not determine this order. Derive it from which intervals are valid candidates and which direction improves the objective.
Trace the shortest nonnegative-sum interval
Use two, one, three, two with target five. Growing the right edge gives sums two, three and six. Record length three, then remove the leading two and stop shrinking at sum four. Adding the final two gives sum six for one, three, two. After recording length three, remove one to obtain sum five and record length two. Removing three makes the sum too small. The best interval is three, two.
Nonnegativity means extension cannot decrease the sum and removing a left element cannot increase it. This monotonicity justifies never returning to an earlier left boundary. Zeros are allowed, but the target is positive and the desired interval is nonempty. A specification allowing empty intervals would need separate boundary handling and must not be silently mixed into this implementation.
| Right index after addition | Shrink trace | Lengths recorded |
|---|---|---|
| 2: add 3 | [2,1,3]:6 → [1,3]:4 | 3 |
| 3: add 2 | [1,3,2]:6 → [3,2]:5 → [2]:2 | 3, then 2 |
Track frequencies rather than only membership
For abac with a limit of two distinct characters, a, ab and aba are valid. Adding c creates three kinds. Removing the first a leaves another a in bac, so three kinds remain. Removing b finally gives ac with two kinds. The maximum valid length was three for aba. A plain set would lose information if it removed a while another copy remained in the window.
Decrease a departing character's count and delete its dictionary entry only when the count reaches zero. The number of entries is then the distinct count. With k equal to zero every nonempty window is repaired to length zero. Python string elements are code points rather than necessarily user-perceived characters; a grapheme-aware product must define its splitting unit before applying the same window logic.
Compare each implementation with interval enumeration
The sum function rejects negative elements with ValueError. It does not repair the input by replacing negatives with zero. The tests enumerate every interval of short nonnegative arrays and compare the smallest valid length. The character function is likewise checked against all substrings. Include empty input, absent solutions, zeros and a zero distinct-character limit.
A missing sum interval returns zero under this contract. Returning the actual interval instead would require saving boundaries whenever a better answer is found. Equal-length candidates would also need a tie rule, such as the earliest interval or all intervals. That ambiguity does not affect a length-only result, but it matters when adapting the function to a product. Match assertions to the promised output rather than an unstated preferred example.
from itertools import product
def minimum_length(a,target):
if target<=0 or any(x<0 for x in a):raise ValueError('nonnegative values, positive target required')
left=0;total=0;best=len(a)+1
for right,x in enumerate(a):
total+=x
while total>=target:
best=min(best,right-left+1);total-=a[left];left+=1
return 0 if best>len(a) else best
def distinct_window(text,k):
if k<0:raise ValueError('negative limit')
counts={};left=0;best=0
for right,c in enumerate(text):
counts[c]=counts.get(c,0)+1
while len(counts)>k:
old=text[left];counts[old]-=1;left+=1
if counts[old]==0:del counts[old]
best=max(best,right-left+1)
return best
for n in range(6):
for a in product(range(3),repeat=n):
for target in range(1,5):
sizes=[j-i for i in range(n) for j in range(i+1,n+1) if sum(a[i:j])>=target]
assert minimum_length(a,target)==min(sizes,default=0)
for text in ['','abac','aaaa','abcabc']:
for k in range(4):assert distinct_window(text,k)==max((j-i for i in range(len(text)+1) for j in range(i,len(text)+1) if len(set(text[i:j]))<=k),default=0)
try:minimum_length([2,-1],2)
except ValueError:pass
else:raise AssertionError('negative input accepted')
print('sum and distinct-count windows matched exhaustive references')
Find the broken rule with a negative value
Consider one, minus one, five and target five. The whole interval first reaches the target. Removing the leading one lowers the sum to four, so the nonnegative algorithm stops shrinking and keeps length three. Removing the next minus one would increase the sum back to five, exposing a one-element answer. The assumption that removing the left edge cannot increase the sum has failed.
This does not mean every window technique rejects negative data. The distinct-character problem is not based on numeric sums at all. A shortest-sum problem with negatives requires a different argument, perhaps using prefix sums and a separate candidate structure. Check how the maintained measure changes under extension and removal. A familiar technique name is not a substitute for a valid monotonicity proof.
Count removals over the whole execution
The right boundary adds each element once. The left boundary never retreats and removes each element at most once. Count those removals over the complete run instead of multiplying a worst-case inner-loop length by every outer iteration. The sum algorithm is O(n); the dictionary version has the same expected bound under the usual average constant-time dictionary assumption. Its storage depends on the number of distinct symbols retained.
Copying each slice or recomputing its sum would invalidate that implementation-cost argument. Locate the incremental addition, subtraction and single-key frequency updates in the code. Theoretical state changes must correspond to the operations actually performed. If integers or key comparisons have nonconstant cost, state that additional computational assumption rather than hiding it behind pointer movement.
Check summary state against the actual interval
When debugging a window, compare its sum or frequency map with the actual slice after each step, not just left and right. In abac, removing the first a must leave frequency one for a. Correct boundaries with an incorrect summary still lead to wrong repair decisions. Small exhaustive references help find cases where an internal-state error changes the final length.
Adding several constraints requires a fresh account of maintained state and repair direction. A longest-window routine should not automatically shrink whenever it becomes valid; that may destroy the candidate it is trying to enlarge. Derive growth, repair and answer-update timing from the objective. A short state table makes adaptations between similar-looking window problems much safer than copying loop shapes alone.
Exercise: check the answer-update position
For aabcc and k equal to two, the repaired windows are a, aa, aab, bc and bcc. The running maxima are one, two, three, three and three. Adding the first c creates three kinds; removing only one a still leaves another a. Both copies must depart before the window becomes valid. Judge the current frequency state, not how many repair steps you expected from an earlier example.
For zero, zero, five with target five, both leading zeros can be removed while the target remains satisfied. The shortest valid interval has length one. Replacing the shrinking while with a single if can miss it. Explain why several left boundaries must be considered for one right endpoint instead of memorizing a rule that every window requires exactly the same loop structure.