The Sliding Window Technique
In programming, the sliding window is a technique or method that can be used to help solve problems. It can be used to make solutions more efficient normally by reducing the time complexity down to O(n).
Like all algorithms or techniques, it is useful with certain problems but obviously not all. If we are looking for a window of values with constraints on the values we want in that window. We also use left and right pointers to be the left and right of the window, it slides along the string or array. The window can also get bigger or smaller by moving the right pointer only or the left pointer only respectively. So that being said it works best in problems that use arrays or strings and we are trying to get a continuous subarray or continuous substring as a result.
Above was a brief explanation of why to use the sliding window technique and some keys on how to spot when to use it. But, a better way to see this technique and understand it is to see it used for a problem. One of the first problems I saw using it as a solution was with the ‘Longest substring without repeating characters’. In this problem, we have to find the longest substring of the input string without any duplicated characters an example of this is ‘hello’ would be 3 — ‘hel’.
To begin creating a function to solve this problem we name variables left and right to be the index of the start and end of our substring respectively (or start and end of window) both set initially to 0. Then also initiate a new Set where we will store the longest substring (a Set is an object where we can store values, you can’t have duplicates in a set). Finally, a variable to store our max substring length.
Next, we add a while loop to move our pointers the loop runs until the right pointer reaches the end of the string. As the loop runs if our right pointer is on a unique character that is not in our set we will add the character to the set, update the max substring length and move the right pointer up. But, if the character at the right pointer already exists in the set we delete the character that the left pointer is pointing to from the set and move the left pointer up closing our window slightly.
When the loop is through running we return the max value we stored when we found the longest substring. Below is this explanation/walkthrough written out in JavaScript:
It is a helpful technique to know as it can improve the time complexity of your code for certain problems.
https://www.geeksforgeeks.org/window-sliding-technique/ explains this technique which helped me get a better understanding.
