Counting windows

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

Counting all valid windows ending at right requires a stronger property: every suffix starting from left through right must also be valid. Then right-left+1 counts them without enumeration.

Work through an example

With at most one distinct value in [1,1,2], contributions are 1,2,1: total 4. Exactly K can be counted as atMost(K)-atMost(K-1).

Time and space complexity

Expected O(n) time and O(K) live distinct-key space; result may be Θ(n²).

Why it works

After repair, all and only starts in [left,right] yield valid windows for this right.

Common mistakes

A count of valid windows is not the same as maximum length.
Define atMost(negative K)=0.

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