Leetcode Pattern: Sliding Windows

TLDR

Expand window -> Check window validity -> If not valid shrink window until valid -> (repeat process)

How to study

1. Understand Neetcode's solution to Leetcode#3
2. Understand the framework below, compare between the framework and Leetcode#3 solution.

Framework:

A = {}
l, r = 0, 0
result = 0

# increase right pointer (expand window)
for r in range(len(input_string)):
    # CODE: use A[r] to update state which might make window invalid
    
    # check whether window valid, if invalid we keep shrinking window until valid
    while (valid_criteria):
        # not valid
        # CODE: update state using A[l]
        # CODE: increase left pointer (shrink window) 
    
    # CODE: max window size

Leetcode#3 Solution:

def longest_substring(s):
    charSet = set()
    l, r = 0, 0
    result = 0

    # increase right pointer (expand window)
    for r in range(len(s)):
        # check whether window is valid
        while s[r] in charSet:
            # update state using A[l] 
            charSet.remove(s[l])
            # if not valid increase left pointer (shrink window) until valid
            l += 1
        # use A[r] to update state which might make window invalid 
        charSet.add(s[r])
        # max window size
        result = max(result, r-l+1)

        # if valid continue increase right pointer (expand window)
    return result

Problems solved using Sliding Window

424. Longest Repeating Character Replacement