Sliding window is a technique wherein we make a window and slide it over an array to access its different parts. This technique is used as it gives us the optimum solution for most subarray-finding problems.
Let's look at an example to understand this better:
LeetCode Problem: 3
Given a string 's', find the length of the longest substring without repeating characters.
We have to find the longest possible substring from a given string, in which no character occurs more than once.
Let us look at a naive bruteforce approach and then optimize the solution using sliding window.
1. Bruteforce Approach (O(n^3))
The naive approach is to check for all possible substrings and find the longest valid one.
We check the substring by taking a boolean array of size 256 for all characters that will maintain a record of the characters that are present in a substring. When we visit a character, we mark its position in the boolean array as true. If while traversing the substring, we come across the same character again, we will know that this is now a repeated character and hence the substring is not valid.
#include <bits/stdc++.h>
using namespace std;
bool areDistinct(string str, int i, int j)
{
vector<bool> visited(256);
for (int k = i; k <= j; k++) {
if (visited[str[k] - 'a'] == true)
return false;
visited[str[k] - 'a'] = true;
}
return true;
}
int longestUniqueSubsttr(string str)
{
int n = str.size();
int res = 0; // result
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = max(res, j - i + 1);
return res;
}
int main()
{
string str = "mrinalini";
int len = longestUniqueSubsttr(str);
cout<< len;
return 0;
}
Here, the function areDistinct considers characters from i to j as a substring and checks if it is a valid string.
One can easily note that this method is redundant as it will repeatedly check for validity of all substrings of the resultant string also, increasing the time complexity of the algorithm.
Sliding Window Approach O(n)
Sliding window eliminates the loop which was independently checking the validity of every substring in the bruteforce method by following a more cumulative approach.
Approach:
Consider the first smallest substring as a window by defining the first element as window's left-most and also right-most element.
Include the element just right of the window end by expanding the window.
Check if the element just included was unique or not, i.e. if it was not already present in the window before expansion.
If not unique, contract the left side of the window until the element just included becomes unique in the current window.
If the current window's length is greater than result, store the new length in result.
We check for the uniqueness of element by making an array of size 256. Whenever we expand and include an element in the window, we increment the value of that character's position in the array. If the value in the array is greater than 1, the element was not unique. Then we decrement all values of array that we exclude from the window by contraction.
int lengthOfLongestSubstring(string str) {
if(str.size()<1)
return 0;
int cur_len =1,max_len=1;
int visited[256];
memset(visited,0,sizeof(visited));
int left=0,right=0;
while(right<str.size()){
int idx=str[right];
visited[idx]++;
while(visited[idx]>1){
int lidx = str[left];
visited[lidx]--;
left++;
}
max_len = max(max_len,right-left+1);
right++;
}
return max_len;
}
This approach requires only two loops, the outer loop increments the right of window (expansion), till it reaches the end of string. The inner loop checks if that element was unique, and if not, contracts the left of the window until that element becomes unique.
The outer loop runs for n times. Let k be the longest possible contraction length. Then time complexity will be O(n*k), i.e, O(n).
Hope you liked this article. Feel free to share your thoughts and connect with me on linkedin .