Sliding Window Technique Simplified (C++)

The Sliding Window Technique is a powerful method to solve problems involving arrays or strings. It optimizes problems that involve contiguous subarrays or substrings, making it more efficient than brute-force approaches.

The main idea is to define a “window” (a portion of the data) that slides across the array or string to perform some operation like calculating a sum, finding the longest/shortest substring, or identifying unique elements. This window can grow or shrink in size as it moves, allowing us to process subsets of data efficiently.

When to Use the Sliding Window Technique:

1. We need to find or process subarrays or substrings (fixed or variable in size) in a larger sequence.
2. We are asked to solve problems like maximum sum of K elements, longest substring with no repeating characters, or smallest subarray with a specific sum.
3. The problem involves continuous sequences, and we want to avoid using nested loops, which may increase time complexity.

Relation to Two Pointers: The two-pointer technique and the sliding window often overlap. In sliding window problems, we have two pointers: one that marks the start of the window and another that marks the end. As the window moves (or “slides”), we adjust these pointers to maintain or adjust the window size. The left pointer shrinks the window, and the right pointer expands it.

Recommended: Please read Two Pointers in C++: A Path to Optimized Algorithms to learn about two-pointer and understand it better.

Types of Sliding?Windows:

• Fixed-size sliding window: The window size is fixed, and you move it across the array.
• Variable-size sliding window: The window size changes dynamically based on certain conditions.

Example 1: Fixed-Size Sliding Window (Maximum Sum of Subarray)

Problem: Given an array, find the maximum sum of a subarray of size K.

#include <iostream>
#include <climits>
using namespace std;

int maxSumSubarray(int arr[], int n, int k) {
    int max_sum = INT_MIN;   // Initialize the maximum sum
    int window_sum = 0;

    // Find the sum of the first 'k' elements
    for (int i = 0; i < k; i++) {
        window_sum += arr[i];
    }

    // Now slide the window across the array
    for (int i = k; i < n; i++) {
        window_sum += arr[i] - arr[i - k];  // Slide the window
        max_sum = max(max_sum, window_sum);  // Update the maximum sum
    }

    return max_sum;
}

int main() {
    int arr[] = {2, 1, 5, 1, 3, 2};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Maximum sum of subarray of size " << k << " is " << maxSumSubarray(arr, n, k) << endl;
    return 0;
}        

Explanation:

• First, we compute the sum of the first K elements.
• As the window slides (by moving both pointers), we update the window sum by adding the new element and subtracting the one leaving the window.
• This algorithm runs in O(N) time, making it much faster than recalculating sums for all subarrays, which would take O(N2).

Example 2: Variable-Size Sliding Window (Smallest Subarray with Sum Greater Than X)

Problem: Given an array, find the smallest subarray with a sum greater than a given value X.

Code Snippet in?C++:

#include <iostream>
#include <climits>
using namespace std;

int smallestSubarrayWithSum(int arr[], int n, int x) {
    int min_len = INT_MAX;
    int start = 0, end = 0, current_sum = 0;
    while (end < n) {
        // Add elements to the current window
        current_sum += arr[end++];
        // Shrink the window from the start if the sum exceeds X
        while (current_sum > x) {
            min_len = min(min_len, end - start);
            current_sum -= arr[start++];
        }
    }
    return (min_len == INT_MAX) ? -1 : min_len;
}
int main() {
    int arr[] = {1, 4, 45, 6, 0, 19};
    int x = 51;
    int n = sizeof(arr)/sizeof(arr[0]);
    int result = smallestSubarrayWithSum(arr, n, x);
    
    if (result == -1) {
        cout << "No subarray found" << endl;
    } else {
        cout << "Smallest subarray length with sum greater than " << x << " is " << result << endl;
    }
    
    return 0;
}        

Explanation:

• Here, the window size varies. We keep expanding the window by moving the right pointer.
• When the window’s sum exceeds the target X, we shrink the window by moving the left pointer to find the smallest possible subarray that meets the condition.

Now, Let’s try to solve some Leetcode Problems:

Example.1 Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you
must buy before you sell.

Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.        

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = prices[0];
        int max_profit = 0;
        for(int i=1; i<prices.size(); i++){
            max_profit = max(max_profit, prices[i]-min_price);
            min_price = min(min_price, prices[i]);
        }
        return max_profit;
    }
};

// Time Complexity : O(n)
// Space Complexity : O(1)        

Example.2 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. 

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and 
not a substring.        

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int max_length = 0;
        unordered_set<char>char_set;

        for(int right = 0; right < s.length(); right++){
            while(char_set.find(s[right]) != char_set.end()){
                char_set.erase(s[left]);
                left++;
            }
            char_set.insert(s[right]);
            max_length = max(max_length, right-left+1);
        }
        return max_length;
    }
};

// Time Complexity : O(n)
// Space Complexity : O(min(n, m)) 
//              (or O(n) in the worst case where all characters are unique).        

Example.3 Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.        

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.length(), most_frequent_element = 0;
        int left = 0, result = 0;
        unordered_map<char, int> count;

        for (int right = 0; right < n; right++) {
            count[s[right]]++;

            // Find the count of the most frequent character in the current window
            most_frequent_element = 0;
            for (auto& pair : count) {
                most_frequent_element = max(most_frequent_element, pair.second);
            }

            int window_size = right - left + 1;

            // If the number of characters that need to be replaced exceeds k, 
            // shrink the window
            if (window_size - most_frequent_element > k) {
                count[s[left]]--;
                left++;
            }

            // Update the result with the maximum window size
            result = max(result, right - left + 1);
        }

        return result;
    }
};

// Time Complexity : O(n), where n is the length of the string s.
// Space Complexity : O(1) (since the count map has a fixed size of at 
//                           most 26 characters).        

We use two pointers, left and right, to define a "window" in the string. As we expand the right pointer, we include more characters in the window. When the number of characters that need to be replaced exceeds k, we move the left pointer to shrink the window.

• left: The start of the sliding window.
• right: The end of the sliding window, moving through each character of the string.
• count: A map that keeps track of the frequency of each character in the current window.
• most_frequent_element: Tracks the highest frequency of any character in the current window.
• result: Stores the maximum length of the valid window encountered.

String:       A   A   B   A   B   B   A
Index:        0   1   2   3   4   5   6
             ↑
            left

First, we start with an empty window. As we expand the window by moving `right`, we add characters to the window.

Sliding Window Example (Step-by-Step):

Step 1: left = 0, right = 0
         Window: A
         Frequency Map: {'A': 1}
         Most Frequent Element: 1 ('A')
         Valid window size: 1
         Max Result: 1

Step 2: left = 0, right = 1
         Window: A A
         Frequency Map: {'A': 2}
         Most Frequent Element: 2 ('A')
         Valid window size: 2
         Max Result: 2

Step 3: left = 0, right = 2
         Window: A A B
         Frequency Map: {'A': 2, 'B': 1}
         Most Frequent Element: 2 ('A')
         Valid window size: 3 (because we can replace 1 'B')
         Max Result: 3

Step 4: left = 0, right = 3
         Window: A A B A
         Frequency Map: {'A': 3, 'B': 1}
         Most Frequent Element: 3 ('A')
         Valid window size: 4
         Max Result: 4

Step 5: left = 0, right = 4
         Window: A A B A B
         Frequency Map: {'A': 3, 'B': 2}
         Most Frequent Element: 3 ('A')
         Invalid window: need 2 replacements (exceeds k = 1)
         Slide left: left = 1

Step 6: left = 1, right = 4
         Window: A B A B
         Frequency Map: {'A': 2, 'B': 2}
         Most Frequent Element: 2 ('A' or 'B')
         Max Result: 4 (still)