Sliding window technique is useful when we want to go through an array of items once and want to compute substring based on various constraints. The solution is usually O(n), alternative approach would have been much more slow if solved the traditional or bruteforce way of nested loops (which usually comes to mind as a newbie DSA solver).
The best way to understand is to look at the problems. Let's go over some problems to understand this technique.
I didn't solve all of the problems given below and sometimes even had to take help. But I did attempt to solve them before seeing a hint or a solution.
Longest substring without repeating characters
This problem is to find the longest substring of unique characters in a given string s. A window can be represented using two pointers left and right. Both are initialized from 0. maxLen is just used to track the max length of window on each iteration (the actual answer for the problem comes from this variable). lettersPresent is a hash map which tracks the last index of a letter before right pointer.
Steps taken to find the answer while right remains smaller than the length of s:
- if current letter (at
right) is not encountered till now calculatemaxLenby comparingmaxLenandright - left + 1and then increment right - if current letter was encountered before and it is inside the window then window can be reduced from the left to just after the last encountered letter
Once the whole iteration is done return maxLen as it represents longest substring containing unique letters.
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let maxLen = 0;
let lettersPresent = {};
let left = 0;
let right = 0;
while (right < s.length) {
const lastIndex = lettersPresent[s[right]];
lettersPresent[s[right]] = right;
if (lastIndex > -1 && lastIndex < right && lastIndex >= left) {
left = lastIndex+1;
} else {
if (maxLen < (right - left + 1)) {
maxLen = right - left + 1;
}
}
right++;
}
return maxLen;
};
Minimum size subarray sum
In this problem, we have an array nums of positive integers and a number target. We have to find out the minimum length of a subarray whose sum is greater than or equal to target. As first part of solving this problem we initialize variable that we are going to use to solve this problem. minLen will track minimum length of array with sum greater than or equal to target. currSum will keep track of sum of elements present in the window. And left and right are pointers that represent the window.
While right is smaller than length of nums array
- add current number (at index
right) tocurrSum - while
currSumis more than equal totarget- update
minLenif current length of window (right-left+1) is smaller than it - substract num at index
leftfromcurrSumas window is decreased by moving left towards right by one index
- update
Return the answer using value of minLen.
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(target, nums) {
let minLen = Infinity, currSum = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
let num = nums[right];
currSum += num;
while (currSum >= target) {
if (right - left + 1 < minLen) {
minLen = right - left +1;
}
currSum -= nums[left];
left++;
}
}
return minLen === Infinity ? 0 : minLen;
};