Sliding Window

Sliding Window Technique

# Fixed window: max sum of k consecutive elements O(n)
def max_sum_k(arr, k):
    window = sum(arr[:k])
    best   = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i-k]  # slide right
        best    = max(best, window)
    return best

# Variable window: longest substring without repeat O(n)
def longest_no_repeat(s):
    char_set = set()
    left = best = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        best = max(best, right - left + 1)
    return best

# Minimum window substring O(n)
from collections import Counter
def min_window(s, t):
    need    = Counter(t)
    missing = len(t)
    lo = best_lo = best_hi = 0
    hi = -1
    for hi, ch in enumerate(s):
        missing -= need[ch] > 0
        need[ch] -= 1
        if not missing:
            while need[s[lo]] < 0: need[s[lo]] += 1; lo += 1
            if not best_hi or hi-lo < best_hi-best_lo:
                best_lo, best_hi = lo, hi
    return s[best_lo:best_hi+1]