• Introduction
• Types of Sliding Window
• Fixed-Size Sliding Window
• Dynamic-Size Sliding Window
• Applications of the Sliding Window Technique
• Run C Programming Online Compiler

¶Introduction

The sliding window technique is a method for iterating through an array or list to find a subset of elements that meet a particular condition. It involves maintaining a window that slides over the array, either by fixing the size of the window or dynamically adjusting it based on the problem’s requirements. The essence of the sliding window technique lies in its ability to reduce the time complexity of certain problems from O(𝑛 ² ) to O(𝑛) by avoiding the need for nested loops. Instead of recomputing the entire subset of elements for each position, the window “slides” over the array, updating the required values incrementally. The sliding window technique is generally used in problems like Checking for the presence of a fixed or dynamic size subarray with certain properties, String problems like finding the longest substring with unique characters or matching patterns.

¶Types of Sliding Window

There are two primary types of sliding windows:

Fixed-Size Sliding Window: The window has a fixed size and slides from the beginning to the end of the array.

Dynamic-Size Sliding Window: The size of the window can expand or contract based on the conditions specified in the problem.

¶Fixed-Size Sliding Window

A fixed-size sliding window is used when the problem requires processing subarrays of a given size. This involves initializing the window with the first set of elements and then moving it one element at a time while updating the necessary values.

Consider an array of integers and we have to find the maximum sum of the all possible subarrays of size k.

To solve this problem, we slide a window of size k across the array. We calculate the sum of elements within the window. In each iteration, we “slide” the window by one element:

1. We remove the element leaving the window from the sum.
2. We add the element entering the window to the sum.
3. We keep track of the maximum sum encountered so far.

This approach has time complexity of O(n) rather than calculating answer using nested loops with O(n * k) time complexity.

#include <stdio.h>

int maxSubarraySum(int arr[], int n, int k) {
    int max_sum = 0;
    int current_sum = 0;

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

    max_sum = current_sum; // Initially, max_sum is the sum of the first window

    // Slide the window
    for (int i = k; i < n; i++) {
        current_sum -= arr[i - k]; // Remove element leaving the window
        current_sum += arr[i];     // Add element entering the window
        max_sum = current_sum > max_sum ? current_sum : max_sum; // Update max_sum if necessary
    }

    return max_sum;
}

int main() {
    int arr[] = {1, 4, 2, 10, 6, 3, 3};
    int k = 3;  // Subarray size
    int n = sizeof(arr) / sizeof(arr[0]);

    int max_sum = maxSubarraySum(arr, n, k);
    printf("Maximum sum of subarray of size %d: %d\n", k, max_sum);

    return 0;
}

¶Dynamic-Size Sliding Window

A dynamic-size sliding window is useful when the problem requires finding subarrays or substrings that satisfy certain conditions, which may cause the window size to change dynamically.

Consider a string and we have to find the length of the longest substring without repeating characters.

To solve this problem, we will again slide a window across the string. This window represents the current substring we’re considering. Unlike the previous example where we calculated sums, we’re interested in finding the longest substring that contains all unique characters. Using a data structure like a hash table (or a simple array for smaller character sets), we’ll keep track of the characters within the window. This allows us to efficiently check if a character has already appeared in the current substring.

As we slide the window:

1. Element Leaving the Window: If the character leaving the window (the one at the leftmost position) already exists in the data structure, it means the current substring is no longer unique. We remove this character from the data structure.

2. Element Entering the Window: Add the character entering the window (the one at the rightmost position) to the data structure.

3. Track the Maximum Length: In each iteration, we check the current window’s length (right index minus left index plus 1). If this length is greater than the currently stored maximum length, we update the maximum length.

This approach has a time complexity of O(n). This is significantly faster than checking every possible substring using nested loops.

#include <stdio.h>
#include <stdbool.h> // for boolean values

int longestUniqueSubstr(char str[], int n) {
  int left = 0, right = 0;
  int max_length = 0;

  // Use an array to track character presence (can replace with a hash table)
  bool char_present[256] = {false}; // Assuming ASCII characters

  while (right < n) {
    

    // Check if character already present (repeated)
    if (char_present[str[right]]) {
      // Slide the window until the repeating character is removed
      while (str[left] != str[right]) {
        char_present[str[left]] = false; // Mark character leaving the window
        left++;
      }
      // Move left pointer one more to exclude the repeated character
      left++;
    }

    char_present[str[right]] = true; // Mark character entering the window
    
    // Update maximum length if necessary
    max_length = (right - left + 1) > max_length ? (right - left + 1) : max_length;

    right++; // Slide the window by one
  }

  return max_length;
}

int main() {
  char str[] = "abcabcbb";
  int length = longestUniqueSubstr(str, 8);
  printf("Length of the longest unique substring: %d\n", length);
  return 0;
}

¶Applications of the Sliding Window Technique

The Sliding Window Technique is versatile and finds applications in various domains:

Natural Language Processing: sliding window is used to extract features or n-grams from text data.

Image Processing: sliding window is used to extract features from different parts of an image. Also used in detecting objects in image by sliding a window across the image and applying a classifier.

Bioinformatics: DNA Sequence Analysis: Analyze DNA sequences to find regions with specific characteristics, like high GC content or motifs.

Signal Processing: Analyze time-series data to capture local patterns, trends, or anomalie. Also sliding window is used to smooth signals and reduce noise.

Array and String Manipulation:

1. Maximum/Minimum Subarray Sum: Efficiently find the subarray with the maximum or minimum sum.
2. Longest Substring Without Repeating Characters: Identify the longest substring with all unique characters.
3. Anagram Checks: Check for anagrams within a string by maintaining a frequency count in a sliding window.

Data Compression: in LZ77 Algorithm a sliding window is used to detect repeated patterns and replace them with references to previous occurrences, leading to data compression.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online