Validity conditions and shrinking

What is a sliding window?

A window is a consecutive part of a sequence. Sliding it means moving its boundaries as you examine the sequence. For a fixed-size window, one item leaves and one enters at each move. Keeping a running total or count lets you reuse work instead of rebuilding it every time.

Example: The size-3 windows in [2, 1, 4, 3] are [2, 1, 4] and [1, 4, 3]. Their totals are 7 and 8. To get the second total, subtract 2 and add 3.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Hash maps and sets

Understand the idea

Choose a validity condition that can be repaired by advancing left. For nonnegative sum-threshold problems, removing elements never increases the sum; this monotonicity justifies shrinking.

Work through an example

For shortest sum≥7 in [2,3,1,2,4,3], grow until valid, record length, and keep shrinking while valid. [4,3] gives length 2.

Time and space complexity

O(n) time/O(1) sum state for nonnegative values; negative inputs invalidate this monotonicity.

Why it works

Before recording a candidate, its sum meets the threshold; each shrink tests the next possible start.

Common mistakes

For shortest valid windows, record before the shrink that invalidates them.
The validity rule differs from longest-valid problems.

Chapter lab · Python implementation

A window represents a contiguous active interval. Reuse its overlapping state when advancing boundaries. The lab finds the longest substring with distinct characters; a fixed-size sum example contrasts automatic eviction with condition-based shrinking. Bounds below count code points, not user-visible grapheme clusters.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def max_window_sum(values,k):
    if not 1<=k<=len(values):
        raise ValueError('invalid k')
    current=0
    for i in range(k):
        current+=values[i]
    best=current
    for right in range(k,len(values)):
        current+=values[right]-values[right-k]
        best=max(best,current)
    return best

def longest_unique(text):
    counts={}
    left=best=0
    for right,char in enumerate(text):
        counts[char]=counts.get(char,0)+1
        while counts[char]>1:
            old=text[left]
            counts[old]-=1
            if counts[old]==0:
                del counts[old]
            left+=1
        best=max(best,right-left+1)
    return best

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert max_window_sum([2,1,5,1,3,2],3)==9
assert max_window_sum([-5,-2,-8],2)==-7
assert longest_unique('abca')==3
assert longest_unique('')==0
assert longest_unique('abba')==2

CHECK YOUR UNDERSTANDING