The sliding window algorithm is a technique used to solve problems that involve finding a subset of data that meets a certain criteria. The subset of data is usually a contiguous set of elements from an array or string.

The basic idea of the sliding window technique is to keep a small subset of data (the “window”) in memory and process it in a sequential manner, moving the window through the data to process all the elements efficiently.

The sliding window technique is a highly efficient way of processing data, as it allows us to only process a small portion of the data at a time, reducing the memory and computational requirements.

Common Use Cases⌗

The concept of the sliding window technique can be applied to many problems, such as finding the maximum or minimum value in an array, counting the number of unique elements in a subarray, and checking if a given string has a repeating pattern. Some common use cases of the sliding window technique include:

  1. String processing: In string processing, the sliding window technique can be used to check if a given string has a repeating pattern or to find the length of the longest substring with no repeating characters.

  2. Array processing: In array processing, the sliding window technique can be used to find the maximum or minimum value in a subarray, or to calculate the sum of all elements in a subarray.

  3. Network communication: In network communication, the sliding window technique is used to manage the flow control of data packets being transmitted over the network.

Steps to Implement the Sliding Window Technique⌗

The basic steps involved in implementing a sliding window technique are:

  1. Define the size of the window and initialise it to the first few elements of the array.

  2. Keep moving the window to the right and updating the values inside the window until it covers all the elements in the array.

  3. For each window, perform the desired operation, such as finding the maximum or minimum value, counting the number of unique elements, or checking for repeating patterns.

  4. Repeat the steps 2 and 3 until the end of the array is reached.

Example⌗

Let’s look at an example of the sliding window technique in action. We’ll use the technique to find the longest substring with no repeating characters in a given string.

The first step is to define the size of the window and initialise it to the first few elements of the data. In this case, we’ll use a window size of 3, which means that the window will contain 3 characters at a time.

    // define window size
    int window_size = 3;

    // initialise window to first 3 characters
    char window[window_size];
    for (int i = 0; i < window_size; i++)
    {
        window[i] = str[i];
    }

Next, we’ll move the window to the right and update the values inside the window until it covers all the elements in the array. For each window, we’ll perform the desired operation, which in this case is to find the longest substring with no repeating characters. This code will be included later, but for now we’ll just write the code to move the window to the right.

    // move window to the right and update values
    for (int i = 0; i < strlen(str) - window_size; i++)
    {
        // find longest substring with no repeating characters
        int len = find_longest_substring(window, window_size);
        if (len > max_len)
        {
            max_len = len;
        }

        // move window to the right
        for (int j = 0; j < window_size - 1; j++)
        {
            window[j] = window[j + 1];
        }
        window[window_size - 1] = str[i + window_size];
    }

Finally, we’ll repeat the steps 2 and 3 until the end of the data is reached. The complete code for this example is shown below (including the code to find the longest substring with no repeating characters).

    #include <stdio.h>
    #include <string.h>

    // Find the longest substring with no repeating characters
    int find_longest_substring(char *str, int len)
    {
        int max_len = 0;
        for (int i = 0; i < len; i++)
        {
            int j;
            for (j = 0; j < i; j++)
            {
                if (str[i] == str[j])
                {
                    break;
                }
            }
            if (j == i)
            {
                max_len++;
            }
        }
        return max_len;
    }

    int main()
    {
        char str[] = "abcabcbb";
        int window_size = 3;
        int max_len = 0;

        // initialise window to first 3 characters
        char window[window_size];
        for (int i = 0; i < window_size; i++)
        {
            window[i] = str[i];
        }

        // move window to the right and update values
        for (int i = 0; i < strlen(str) - window_size; i++)
        {
            // find longest substring with no repeating characters
            int len = find_longest_substring(window, window_size);
            if (len > max_len)
            {
                max_len = len;
            }

            // move window to the right
            for (int j = 0; j < window_size - 1; j++)
            {
                window[j] = window[j + 1];
            }
            window[window_size - 1] = str[i + window_size];
        }

        printf("Longest substring with no repeating characters: %d", max_len);
        return 0;
    }