🧩 Python DSA Patterns — Sliding Window (Advanced) 🪟🔥

The advanced sliding window pattern is used when the window size changes dynamically. You expand the window by moving the right pointer, and whenever the condition becomes invalid, you shrink from the left until it becomes valid again.

This pattern is essential for substring search, frequency-based problems, and continuous range queries.

📝 Longest Substring Without Repeating Characters

Use a set to track repeating characters — expand the window, shrink when duplicate appears.

def longest_unique_substring(s: str) -> int:
    left = 0
    seen = set()
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    print("Longest Unique Substring Length:", max_len)

📝 Longest Substring With At Most K Distinct Characters

Maintain a frequency map → shrink window when distinct count exceeds K.

from collections import defaultdict

def longest_k_distinct(s: str, k: int) -> int:
    left = 0
    freq = defaultdict(int)
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1

        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    print(f"Longest Substring With ≤{k} Distinct Characters:", max_len)

📝 Minimum Window Substring

Find the smallest window that contains all characters of t.

Expand window → when valid, shrink from left to minimize.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""

    need = Counter(t)
    have = {}
    required = len(need)
    formed = 0

    left = 0
    ans = (float("inf"), 0, 0)

    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1

        if ch in need and have[ch] == need[ch]:
            formed += 1

        while left <= right and formed == required:
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)

            have[s[left]] -= 1
            if s[left] in need and have[s[left]] < need[s[left]]:
                formed -= 1
            left += 1

    if ans[0] == float("inf"):
        return ""

    result = s[ans[1]:ans[2] + 1]
    print("Minimum Window Substring:", result)
    return result

📝 Sliding Window Maximum

Use a deque to maintain decreasing elements — the front always holds the max.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()
    result = []

    for i in range(len(nums)):
        if dq and dq[0] == i - k:
            dq.popleft()

        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    print("Sliding Window Maximum:", result)

🧠 Where It Helps

• Longest unique substring
• K distinct characters
• Minimum window substring
• Maximum/minimum of every window
• All frequency-based substring problems

Sliding window reduces many O(n²) brute-force substring algorithms to O(n).

🧠 Takeaway

• Expand right pointer → analyze condition
• Shrink left pointer when invalid
• Use sets, maps, counters, or deque depending on problem
• This is the most reused template in string/window problems

🏋️ Practice Problems

1. Minimum Window Substring
2. Longest Substring Without Repeating Characters
3. Longest Substring With K Distinct Characters
4. Sliding Window Maximum
5. Fruits Into Baskets (2 distinct characters)

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns