C++ In Practice - Sliding Window

Sliding Window (C++11 Deep Dive)

The Sliding Window technique is a subset of the Two Pointer pattern. It transforms nested loops (O(N^2)) into a single pass (O(N)) by maintaining a "window" of state. In C++11, efficient implementation relies on choosing the right container for the "state" (e.g., std::vector vs std::unordered_map) to keep the inner operations O(1).

---

1. The Core Template & Data Structures

Optimization Strategy: In problems involving characters (A-Z, a-z, ASCII), avoid std::unordered_map if possible.

• Why? hashing overhead and potential collisions.
• Alternative: Use a fixed-size std::vector<int> or raw array int count[128] (or 256). Access is strict O(1).

The C++11 Template:

int slidingWindow(const std::string& s) {
    int left = 0, right = 0;
    int maxLen = 0;
    
    // State: specialized frequency map for ASCII
    std::vector<int> window(128, 0); 
    
    while (right < s.size()) {
        // 1. Expand Window
        char c = s[right];
        window[c]++;
        
        // 2. Contract Window (while constraint is violated)
        while (/* condition invalid */) {
            char d = s[left];
            window[d]--;
            left++;
        }
        
        // 3. Update Result
        maxLen = std::max(maxLen, right - left + 1);
        
        right++;
    }
    return maxLen;
}

---

2. Longest Substring Without Repeating Characters

Problem: Find max length of substring with unique chars.

Complexity: Time O(N) | Space O(1) (fixed alphabet size).

C++11 Implementation: We use a vector of size 128 to store the index of the character + 1. If we see a character again, we jump left directly to index + 1, skipping the while-loop contraction entirely (an optimization).

#include <string>
#include <vector>
#include <algorithm> // for std::max

int lengthOfLongestSubstring(std::string s) {
    // Map char to its last seen index. 
    // Init with -1 or handle 0 carefully.
    std::vector<int> lastIndex(128, -1);
    int maxLen = 0;
    int left = 0;

    for (int right = 0; right < s.length(); ++right) {
        char c = s[right];

        // If character seen and is inside the current window
        if (lastIndex[c] >= left) {
            // Move left to right after the previous occurrence
            left = lastIndex[c] + 1;
        }

        // Update the last seen index
        lastIndex[c] = right;
        maxLen = std::max(maxLen, right - left + 1);
    }

    return maxLen;
}

---

3. Minimum Window Substring

Problem: Smallest substring of s containing all chars of t.

Complexity: Time O(N) | Space O(1) (limited by alphabet).

Deep Dive: This is the hardest standard sliding window problem.

• State: vector<int> need(128, 0) stores count of chars in t.
• Counter: missing tracks how many distinct characters (or total characters) we still need.
• Result: Store start index and len, not the substring itself, to avoid $O(N)$ string copying during updates. Only substring at the very end.

#include <string>
#include <vector>
#include <climits>

std::string minWindow(std::string s, std::string t) {
    std::vector<int> need(128, 0);
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int minLen = INT_MAX;
    int minStart = 0;
    int missing = t.length(); // Total characters required

    while (right < s.length()) {
        // 1. Expand
        // If s[right] is a char we need (count > 0), decrement missing count
        if (need[s[right]] > 0) {
            missing--;
        }
        // Decrement the count in map (can go negative for unneeded chars)
        need[s[right]]--;
        right++;

        // 2. Contract
        // When missing == 0, we have a valid window. Try to shrink it.
        while (missing == 0) {
            // Update result if this window is smaller
            if (right - left < minLen) {
                minLen = right - left;
                minStart = left;
            }

            // We are about to remove s[left]
            need[s[left]]++;
            
            // If the count becomes positive, it means we needed this char
            // and we just lost it from the window.
            if (need[s[left]] > 0) {
                missing++;
            }
            left++;
        }
    }

    return (minLen == INT_MAX) ? "" : s.substr(minStart, minLen);
}

---

4. Longest Repeating Character Replacement

Problem: Replace at most k chars to get same-char substring.

Logic: WindowLength - MaxFrequencyChar <= k.

Complexity: Time O(N) | Space O(1).

#include <string>
#include <vector>
#include <algorithm>

int characterReplacement(std::string s, int k) {
    std::vector<int> counts(26, 0); // Assuming Uppercase A-Z
    int maxCount = 0; // Count of the most frequent char in current window
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < s.length(); ++right) {
        counts[s[right] - 'A']++;
        
        // Optimization: We don't need to scan the whole vector to find maxCount.
        // It only changes if the current char's count exceeds previous max.
        maxCount = std::max(maxCount, counts[s[right] - 'A']);

        // Check validity: (Window Size) - (Most Frequent Char) = (Replacements Needed)
        // If Replacements > k, shrink window.
        // Note: We use 'if' instead of 'while' here (tricky optimization).
        // The window size will stagnate until we find a "better" density, 
        // effectively preserving the largest valid window size seen so far.
        if ((right - left + 1) - maxCount > k) {
            counts[s[left] - 'A']--;
            left++;
        }

        maxLen = std::max(maxLen, right - left + 1);
    }
    return maxLen;
}

---

5. Permutation in String

Problem: Check if s2 contains a permutation of s1.

Pattern: Fixed-size Sliding Window.

Complexity: Time O(N) | Space O(1) (26 chars).

C++11 Approach: Compare two frequency vectors. std::vector operator== performs element-wise comparison, which is constant time for fixed size 26.

#include <string>
#include <vector>

bool checkInclusion(std::string s1, std::string s2) {
    if (s1.size() > s2.size()) return false;

    std::vector<int> s1Map(26, 0);
    std::vector<int> s2Map(26, 0);

    // Initialize the first window
    for (int i = 0; i < s1.size(); ++i) {
        s1Map[s1[i] - 'a']++;
        s2Map[s2[i] - 'a']++;
    }

    // Sliding the window
    for (int i = 0; i < s2.size() - s1.size(); ++i) {
        if (s1Map == s2Map) return true; // O(1) comparison (26 ints)

        // Slide: remove left, add right
        s2Map[s2[i] - 'a']--;
        s2Map[s2[i + s1.size()] - 'a']++;
    }

    return s1Map == s2Map;
}

---

6. Sliding Window Maximum (The Hard One)

Problem: Find the max element in every window of size k.

Container: std::deque (Double-Ended Queue).

Complexity: Time O(N) | Space O(k).

Under the Hood: We maintain a Monotonic Decreasing Queue. The deque stores indices.

1. Remove indices out of the current window from the front.
2. Remove indices whose values are smaller than nums[i] from the back (they are useless because nums[i] is newer and larger).
3. Add nums[i] to the back.
4. The front of the deque is always the index of the maximum element.

#include <vector>
#include <deque>

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::vector<int> result;
    std::deque<int> dq; // Stores INDICES

    for (int i = 0; i < nums.size(); ++i) {
        // 1. Remove indices that are out of this window
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }

        // 2. Maintain Monotonic Decreasing property
        // Remove elements smaller than current from the back
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 3. Add current index
        dq.push_back(i);

        // 4. Add result (only after first window is formed)
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

ASCII Visualization: Monotonic Deque

**Input:** `[1, 3, -1, -3, 5]`, `k=3`

**Step 1 (i=0, val=1):** `dq: [0]` (val: 1)
**Step 2 (i=1, val=3):** 3 > 1. Pop 0. `dq: [1]` (val: 3)
**Step 3 (i=2, val=-1):** -1 < 3. Push. `dq: [1, 2]` (vals: 3, -1). **Max: 3**
**Step 4 (i=3, val=-3):** Window moves. `dq` front is 1 (index). valid.
   -3 < -1. Push. `dq: [1, 2, 3]` (vals: 3, -1, -3). **Max: 3**
**Step 5 (i=4, val=5):** Window moves. `dq` front is 1. valid.
   5 > -3 (pop). 5 > -1 (pop). 5 > 3 (pop). 
   `dq: [4]` (val: 5). **Max: 5**

Summary of Sliding Window Patterns

Problem Type	State Container	Key Logic
Max/Min Length	vector<int> (Freq)	Expand right, while invalid shrink left.
Fixed Window	vector<int> (Freq)	right expands, left increments strictly with right.
String Permutation	vector compare	v1 == v2 is efficient for fixed alphabet.
Window Maximum	std::deque	Monotonic Queue (Indices). Front = Max.
Exact Count	count variable	Maintain count of matching distinct chars to avoid looping map.