🪟 Sliding Window Technique

Sliding Window is a fundamental technique used for solving problems involving contiguous subarrays or substrings. It optimizes problems that would otherwise require nested loops by maintaining a dynamic window that expands and contracts based on a condition.

📑 Table of Contents

Overview & Keywords
Types of Sliding Window
Core Templates
Key Patterns
Practice Problems

Overview & Keywords

Common problem indicators:

longest / smallest
maximum / minimum
subarray / substring
at most / at least K distinct
average of size K
contiguous elements

Types of Sliding Window

1️⃣ Fixed-Size Window (size = K)

Use when window size is constant.

Common Use Cases:

Max sum of subarray of size K
First negative number in every window of size K
Average of every subarray of size K

2️⃣ Variable-Size Window (Stretch/Shrink)

Use when window grows and shrinks dynamically based on a condition.

Common Use Cases:

Longest substring without repeating characters
Longest subarray with sum ≤ K
Minimum window substring
Fruits into baskets (at most K distinct elements)

Core Templates

🔶 Template 1: Fixed Size Window

int left = 0;
long long sum = 0, best = 0;

for (int right = 0; right < n; right++) {
    sum += arr[right]; // expand window

    if (right - left + 1 == K) {
        best = max(best, sum); // process window
        sum -= arr[left]; // shrink
        left++;
    }
}

🔶 Template 2: Variable Window (Universal)

int left = 0;
for (int right = 0; right < n; right++) {
    // Add arr[right] to window

    while (window_condition_invalid) {
        // Shrink window from left
        left++;
    }

    // Update answer with current window [left, right]
}

🔶 Template 3: Frequency Map (Substring Problems)

unordered_map<char, int> freq;
int left = 0;

for (int right = 0; right < s.size(); right++) {
    freq[s[right]]++;

    while (condition_invalid) {
        freq[s[left]]--;
        if (freq[s[left]] == 0) freq.erase(s[left]);
        left++;
    }

    ans = max(ans, right - left + 1);
}

Key Patterns

Pattern	Condition	Trigger	Use When
No Repeating	Any char count > 1	Shrink until all freq = 1	Longest substring without repeating chars
At Most K Distinct	freq_map.size() > K	Shrink until size ≤ K	Max subarray with ≤ K distinct elements
Sum ≤ Target	sum > target	Shrink until sum ≤ target	Min subarray, max subarray with constraint
Two Hash Maps	Elements not in target	Shrink while valid	Minimum window substring
Fixed Size	window size = K	Always process at size K	Fixed window problems