ZERO / HERO
A window sliding along a train

Sliding Window

The analogy

You want the best stretch of carriages under some rule. Instead of measuring every possible stretch, you keep a window and slide it: push the right edge outwards to grow, and when the rule breaks, pull the left edge in until it holds again. Each carriage is entered once and left once.

Visualizer

The window slides

step 1 / 17
LO
A
0
A
1
B
2
C
3
B
4
B
5
A
6
C
7

Find the longest stretch of "AABCBBAC" containing at most 2 distinct letters. Checking every substring is O(n²).k = 2 distinct allowed

from collections import Counter, deque

def longest_at_most_k_distinct(s, k):
    count, lo, best = Counter(), 0, 0
    for hi, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:          # invariant broken
            count[s[lo]] -= 1
            if count[s[lo]] == 0:
                del count[s[lo]]
            lo += 1                    # shrink from the left
        best = max(best, hi - lo + 1)
    return best

def max_in_windows(a, k):              # monotonic deque, O(n)
    dq, out = deque(), []
    for i, v in enumerate(a):
        while dq and a[dq[-1]] <= v:
            dq.pop()                   # smaller values are useless
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(a[dq[0]])
    return out
Check yourself

The array contains negative numbers and you want the shortest subarray summing to at least S. Is a sliding window valid?