Sliding Window

Maintain a variable-size window [l, r]. Expand r to add elements; shrink l when the constraint is violated. Converts O(n²) substring/subarray brute-force into O(n).

// Template

def sliding_window(s):
    l = 0
    window = {}   # or set(), or counter
    result = 0
    for r in range(len(s)):
        # 1. ADD s[r] to window
        # 2. SHRINK from left while constraint violated
        while invalid(window):
            # remove s[l] from window
            l += 1
        # 3. UPDATE result with current valid window
        result = max(result, r - l + 1)
    return result

Easy Best Time to Buy & Sell Stock

INSIGHT: Track min price seen so far. Max profit = current price - min price.

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit
# Time: O(n) | Space: O(1)

Medium Longest Substring Without Repeating Chars

INSIGHT: Use a set as the window. When s[r] already in set, shrink from left until it's gone.

def lengthOfLongestSubstring(s):
    char_set = set()
    l = 0
    max_len = 0
    for r in range(len(s)):
        while s[r] in char_set:
            char_set.remove(s[l])
            l += 1
        char_set.add(s[r])
        max_len = max(max_len, r - l + 1)
    return max_len
# Time: O(n) | Space: O(min(n, alphabet))

Medium Longest Repeating Character Replacement

KEY FORMULA: (window size) - (max freq char count) ≤ k → valid window. If greater, shrink from left.

def characterReplacement(s, k):
    count = {}
    l = 0
    max_count = 0  # max freq char in current window
    max_len = 0
    for r in range(len(s)):
        count[s[r]] = count.get(s[r], 0) + 1
        max_count = max(max_count, count[s[r]])
        # replacements needed = window_size - max_count
        while (r - l + 1) - max_count > k:
            count[s[l]] -= 1
            l += 1
        max_len = max(max_len, r - l + 1)
    return max_len
# Time: O(n) | Space: O(26)=O(1)

Hard Minimum Window Substring

INSIGHT: Track formed = how many chars meet their required count. When formed == required, try shrinking. O(n+m).

from collections import Counter

def minWindow(s, t):
    if not t: return ""
    need = Counter(t)
    have, formed, required = {}, 0, len(need)
    l = 0; min_len = float('inf'); result = ""
    for r in range(len(s)):
        c = s[r]
        have[c] = have.get(c, 0) + 1
        if c in need and have[c] == need[c]:
            formed += 1
        while formed == required:
            if (r - l + 1) < min_len:
                min_len = r - l + 1
                result = s[l:r+1]
            have[s[l]] -= 1
            if s[l] in need and have[s[l]] < need[s[l]]:
                formed -= 1
            l += 1
    return result
# Time: O(n+m) | Space: O(m)

Hard Sliding Window Maximum

INSIGHT: Monotonic deque (decreasing). Front = max of window. Before adding, pop smaller elements from back — they'll never be the max.

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()   # stores indices; front = max of window
    result = []
    for i in range(len(nums)):
        # Remove indices outside window
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order: pop smaller elements
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result
# Time: O(n) | Space: O(k)

← Two Pointers Binary Search →