Window state and frequency maps

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

Store exactly the information needed to add and remove an element: sums, frequencies, distinct counts, or index deques. A frequency map records multiplicity; membership alone can be insufficient.

Work through an example

In 'abba', counts before repair are {a:1,b:2}. Evict a, then the first b; the remaining map is {b:1}.

Time and space complexity

Expected O(1) per frequency update; O(σ) live keys in this implementation.

Why it works

Counts describe precisely the active interval, with zero-count keys removed when distinct-key count matters.

Common mistakes

A set cannot represent duplicate multiplicity directly.
Stale zero-count keys inflate len(counts).

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