Sliding Window (Variable Size)

Overview

The Variable Size Sliding Window technique is a powerful pattern used to solve problems involving subarrays or substrings where the window size is not fixed and depends on a condition.

Unlike fixed-size sliding windows, here the window expands and contracts dynamically based on constraints such as sum, frequency, distinct count, etc.

---

When to Use Variable Sliding Window

Use this pattern when:

• You are dealing with continuous subarrays / substrings
• Window size is not predefined
• The problem asks for:
  • Longest / Shortest subarray
  • At most K / At least K / Exactly K
  • A constraint that must be maintained dynamically

Typical Problem Statements

• Longest subarray with sum ≤ K
• Smallest subarray with sum ≥ K
• Longest substring with at most K distinct characters
• Minimum window substring
• Longest substring without repeating characters

---

Core Intuition

We maintain a window [left, right] such that:

• right pointer expands the window
• left pointer shrinks the window when constraints are violated
• The window always represents a valid candidate

---

General Algorithm Template

initialize left = 0
initialize required data structures (sum, hashmap, count, etc.)
initialize answer

for right in range(0, n):
include arr[right] in window

while window condition is violated:
remove arr[left] from window
left += 1

update answer using (right - left + 1)

---

Key Properties

• Each element is visited at most twice
• Time Complexity: O(N)
• Space Complexity: O(1) or O(K) depending on data structures

---

Example 1: Longest Subarray with Sum ≤ K

Problem

Given an array of positive integers and an integer K, find the length of the longest subarray whose sum is ≤ K.

Approach

• Expand right and add elements to sum
• If sum > K, shrink from left
• Update max length whenever window is valid

Code

python
def longest_subarray_sum_at_most_k(nums, k):
    left = 0
    window_sum = 0
    max_len = 0

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

        while window_sum > k:
            window_sum -= nums[left]
            left += 1

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

    return max_len
Example 2: Smallest Subarray with Sum ≥ K
Problem
Find the length of the smallest subarray whose sum is ≥ K.

Approach
Expand window until sum ≥ K

Shrink from left to minimize window

Keep updating minimum length

Code
def smallest_subarray_sum_at_least_k(nums, k):
    left = 0
    window_sum = 0
    min_len = float('inf')

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

        while window_sum >= k:
            min_len = min(min_len, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return min_len if min_len != float('inf') else 0
Example 3: Longest Substring with At Most K Distinct Characters
Problem
Given a string s, find the length of the longest substring with at most K distinct characters.

Approach
Use a frequency hashmap

Expand right, add characters

If distinct count > K, shrink from left

Code

from collections import defaultdict

def longest_substring_k_distinct(s, k):
    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)

    return max_len


Exactly K Pattern (Important Trick)
Problems asking for exactly K can often be solved using:

Exactly K = At Most K - At Most (K - 1)
Example
Subarrays with exactly K distinct integers

Common Mistakes
Forgetting to shrink the window

Updating answer before the window becomes valid

Using this pattern for subsequence problems (it works only for subarrays/substrings)

Applying it to arrays with negative numbers (sum-based window breaks)

Checklist to Identify Variable Sliding Window
Ask yourself:

Is the data continuous?

Is the window size dynamic?

Is there a constraint to maintain?

Can expanding and shrinking solve it in linear time?

If yes → Sliding Window (Variable)