[Leetcode Pattern] Sliding Window

Sliding windowe is a special kind of two pointers. This technique is often used to find extremum (longest / maximum / minimum …. ) len of subarray / substring.

Basic Template

Window is a variant length (distance between left / right pointer). Forward right pointer until specific constraint is reached. The window len is the possible extremum that gradually extends. When constraint is reached, update extremum with current window len. To search new possible extremum, forward left pointer until window len no longer breaking constraint, and right pointer is ready for new search.

ex: Minimum Size Subarray Sum

n, i, j, = len(nums), 0, 0
wndwLen -> extremum to update
wndwSum -> variable to compare with constraint
while j<n:
    increment nums[j] on wndwSum
    while wndwSum reaches constraint:
        update wndwLen here if target is min
        # shift left to make constraint no longer holds       
        decrement nums[i] on wndwSum
        i+=1  
    update wndwLen here if target is max
    j+=1

Use counter to verify constraint

A counter may count the elms’ frequency within the window. Some constraint requires the frequency info to be compared with.

ex: Longest Substring Without Repeating Characters, Fruit Into Baskets, Longest Repeating Character Replacement

n, i, j, = len(nums), 0, 0
wndwLen -> extremum to update
counter -> count frequency within the window
while j<n:
    increment nums[j] on counter
    while wndwSum reaches constraint:
        update wndwLen here if target is min
        # shift left to make constraint no longer holds       
        decrement nums[i] on counter
        i+=1  
    update wndwLen here if target is max
    j+=1