Sliding Windows

Fixed and variable windows

A fixed-size window slides by adding the new element and removing the old one, so each window costs O(1). A variable window expands the right edge and shrinks the left edge while a condition is violated (a repeated character, a sum above a limit), tracking the best valid window. Every index enters and leaves once, so the total is O(n).

Longest substring without repeats and maximum fixed-window sum, run

I ran this with Python 3.12.3 (standard library only). The variable window returns the actual substring for each test, including the empty string; the best sum of three consecutive numbers is 9 (5 + 1 + 3).

# Variable sliding window: longest substring without repeating characters
def longest_unique(s):
    last, start, best = {}, 0, (0, 0)
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1         # shrink past the previous occurrence
        last[ch] = i
        if i - start + 1 > best[1] - best[0]:
            best = (start, i + 1)
    return s[best[0]:best[1]]

# Fixed window: maximum sum of any k consecutive numbers
def max_window_sum(nums, k):
    cur = best = sum(nums[:k])
    for i in range(k, len(nums)):
        cur += nums[i] - nums[i - k]
        best = max(best, cur)
    return best

for s in ("abcabcbb", "bbbbb", "pwwkew", ""):
    print(repr(s), "->", repr(longest_unique(s)))
print(max_window_sum([2, 1, 5, 1, 3, 2], 3))

Output:

'abcabcbb' -> 'abc'
'bbbbb' -> 'b'
'pwwkew' -> 'wke'
'' -> ''
9

Write the invariant down

"The window [start, i] has no repeated characters" makes the shrinking rule obvious.

त्वरित जाँच: Why is a variable sliding window O(n) despite having a nested shrink step?

• Python optimises it
• The inner loop never runs
• Each index is added and removed at most once
• Because the input is sorted