🚀 Dynamic Sliding Window Technique

The Dynamic Sliding Window technique is an optimization over the fixed-size sliding window. Instead of keeping the window at a constant size, we dynamically expand and shrink the window based on constraints.

---

🔹 Key Concept

The window expands until the constraint is violated and shrinks until it becomes valid again.
The main idea is to use a two-pointer (left-right) approach where:

• Expand right to include more elements.
• Shrink left when a condition is violated.

This method is highly effective in subarray problems, frequency-based problems, and problems with constraints.

---

🔹 When to Use Dynamic Sliding Window?

• Finding longest/shortest subarray that meets a condition.
• Problems with constraints (e.g., maximum replacements allowed, sum conditions).
• Problems where we need to track frequency/count of elements in a window.

---

🛠 Key Patterns in Dynamic Sliding Window

1️⃣ Longest Subarray with a Constraint

You keep expanding the window and shrink only when needed.

🔹 Example 1: Longest Substring with At Most K Distinct Characters

from collections import defaultdict

def longestSubstringKDistinct(s, k):
    char_count = defaultdict(int)
    left = 0
    max_length = 0

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

        while len(char_count) > k:  # More than k distinct chars
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1  # Shrink window

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

    return max_length

✅ Expands until it violates the constraint (more than k distinct chars).
✅ Shrinks until it meets the constraint again.

---

2️⃣ Smallest Subarray with a Constraint

🔹 Example 2: Smallest Subarray with Sum ≥ S

def minSubArrayLen(target, nums):
    left = 0
    curr_sum = 0
    min_length = float('inf')

    for right in range(len(nums)):
        curr_sum += nums[right]

        while curr_sum >= target:
            min_length = min(min_length, right - left + 1)
            curr_sum -= nums[left]  # Shrink window
            left += 1

    return min_length if min_length != float('inf') else 0

✅ Expands while sum is below target.
✅ Shrinks to find the smallest valid subarray.

---

3️⃣ Longest Subarray with K Replacements (Binary or 1s/0s Problems)

🔹 Example 3: Longest Subarray of 1s After Replacing at Most K Zeros

def longestOnes(nums, k):
    left = 0
    max_length = 0
    zeros_count = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros_count += 1

        while zeros_count > k:
            if nums[left] == 0:
                zeros_count -= 1
            left += 1  # Shrink window

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

    return max_length

✅ Expands while zeros_count ≤ k.
✅ Shrinks only when zeros_count > k.

---

🔹 Complexity Analysis

For all Dynamic Sliding Window problems:

• Time Complexity: O(N) (each element is visited at most twice).
• Space Complexity: O(1) (constant space unless storing elements).

---

🔹 Summary Table

Problem Type Pattern Example

Longest Subarray with a Constraint	Expand → Shrink	Longest substring with k distinct chars
Smallest Subarray with a Constraint	Expand → Shrink to minimize	Smallest subarray with sum ≥ S
Replacing Elements in a Window	Expand → Shrink when replacements exceed limit	Longest subarray of 1s after replacing k 0s

---

🔹 Key Takeaways

✅ Expand as much as possible until a condition breaks.
✅ Shrink only when necessary to regain validity.
✅ Time Complexity is O(N), making it much faster than brute force.

Would you like a visual explanation for any of these problems? 🚀