The sliding window is an algorithm typically used for strings or arrays, which allows analyzing a subset of data using a window of fixed or dynamic size. Simply put, the window, in this case, is a substring or subarray. This window can be moved forward across the data set, effectively analyzing changes within the window without having to recalculate it entirely each time. For instance, this algorithm can be used to find the subarray of minimal length whose sum of elements is greater or equal to a given number N or to find the longest substring without repeating characters.
The efficiency of the algorithm comes from the fact that each element is examined only once, thus achieving linear complexity O(n). This is a significant advantage over the brute force approach, which requires a nested loop and results in quadratic complexity O(n²).
2) Start shifting/expanding the window. Move the right pointer to consider more elements.
3) Check the conditions within the current window. As soon as the conditions are not met, move the left pointer until the given conditions are satisfied again.
4) Repeat steps 2 and 3 until the end is reached (when the right pointer hits the end of the array/string).
The essence of the task is simple. Given a string s
, it is necessary to find the longest substring that does not contain repeating characters. This task can simply be solved by brute force, using a nested loop to build all possible substring options and analyze them. However, this approach is highly inefficient with quadratic complexity, O(n²). The task can be solved more optimally using the sliding window. Here are the steps to follow:
Initialize the left and right pointers at position 0. Initialize an empty hash to store discovered characters, allowing us to quickly answer whether we have already seen a character and at what position. Also, initialize a variable to store the found substring.
While the right pointer has not reached the end of the string, check if the character at the right pointer exists in our hash.
2.1. If not, add the character to the hash and move the right pointer. Essentially, the hash records the character and the position it was found.
2.2. If it exists, compare whether the current substring between the left and right pointer is longer than the previously found substring. If yes, update the substring variable. Also, the current window can no longer be moved right; it needs to be narrowed from the left until the current character is unique in the hash. Since the position of the character(where it was found) is stored in the hash, the left pointer can be moved to the right of this character’s position. Thus, we once again have a window with unique characters inside.
Repeat step 2 until the right pointer reaches the end of the string.
const lengthOfLongestSubstring = function(s) {
let hash = {};
let left = 0;
let right = 0;
let maxSubStr = '';
while (right < s.length) {
const char = s[right];
if (char in hash && hash[char] >= left) {
left = hash[char] + 1;
}
hash[char] = right;
const curSubStr = s.slice(left, right + 1);
if (maxSubStr.length < curSubStr.length) {
maxSubStr = curSubStr;
}
right++;
}
return maxSubStr;
};
There is an array of numbers and a given number target. It is necessary to find the subarray of minimal length, the sum of whose elements is greater than or equal to the target. As in the previous example, this task could be solved using a nested loop, building all possible subarrays from each index. Consider how the sliding window allows solving this task more optimally:
const minSubArrayLen = function(target, nums) {
let left = 0;
let right = 0;
let minLen = Infinity;
let curSum = 0;
while (right < nums.length) {
curSum += nums[right];
while (curSum >= target) {
minLen = Math.min(minLen, right - left + 1);
curSum -= nums[left];
left++;
}
right++;
}
return isFinite(minLen) ? minLen : 0;
};
Thus, we have looked at what the sliding window method is and how it can be useful in solving various tasks. This algorithm is particularly effective when analyzing subsequent parts of data because its main advantage is the ability to ensure linear execution time through the efficient reuse of results from previous calculations. I hope this was interesting and clear, and you will be able to apply the full potential of this method to solve your tasks.