Essentially speaking, Sliding Window is to create a sub-list that runs over the underlying collection to search for the answer to the problem. It is often used to solve a problem that asks for an answer of some ranges inside a given collection such as an array or a string.
Keywords to look for in the problems you may consider using this approach to solve: array, string, contiguous subarray, contiguous substring.
questions to ask: does the window needs to be closed?
Let’s take a typical problem called Longest Substring Without Repeating Characters from Leetcode as an example.
The obvious solution to this problem of course is the Brute Force approach. To loop through the string starting from the first character, nest another loop to find the longest non-repeating substring starting from the character. The time complexity of this approach here is O(n²).
The Sliding Window approach is a time-effective approach here.
Basic Sliding Window structure
There is a basic sliding window structure.
1) rightIndex: the endpoint of the window.
2) leftIndex: the starting point of the window.
3) res: the resolution to the problem
4) windowArr: the array that keeps track of amounts of all the characters in the window.
Above is only the basic structure, there will be more things to keep track of for different specific problems.
Solving the example problem
The basic logic for solving it with Sliding Window is that the window will keep expanding (the right index will keep moving to the right) when there is no repeating character in the window. But the window will start getting smaller (the left index moves to the right) when a repeating character appears in the window. And it will keep getting smaller until there isn’t any repeating character left anymore. Then the window can start expanding again.
The resolution will be the largest window size that happened in the loop.
Please see below sudo code in Java.
The time complexity of this solution is O(n), which is a lot better than Brute Force.
Sliding Window for advanced problem
Let’s look at another Leetcode problem that can be solved with the sliding window approach. Longest Repeating Character Replacement. And this time, we don’t close the window.
The basic logic to solving this problem is to find the max amount of identical characters that occurred in the window.
The window will expand when the characters in the window are identical or the number of variants(not the major character in the window)≤ k. The max length = the max window size. However, when the number of variants > k, the window will get smaller by moving the left index by 1. As we are looking for the max length(max window size), there is no point to shrink the window size by keeping on moving the left index to the right, we move the whole window until we can expand the window again.
