What is the Sliding Window Technique? 🤔
The sliding window technique is a common algorithmic strategy used to solve problems involving arrays, strings, or sequences where you maintain a dynamic "window" of elements and slide it through the data to perform specific operations or calculations efficiently. The window is typically defined by two pointers, often referred to as the "left" and "right" pointers, and it represents a subset of the elements within the given data structure.
Visualize Sliding Window 👀:
When to use the technique (key terms):
- Maximum
- Minimum
- Longest
- Shortest
- Sum
- Product
- Subarray
- Substring
- Array
- String
Example LeetCode problems:
Code walkthrough :
Longest Substring Without Repeating Characters
Problem Description:
Given a string s, find the length of the longest
substring
without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution:
var lengthOfLongestSubstring = function(s) {
// Initialize a set to keep track of characters inside the current window
const charSet = new Set();
// initialize two pointers to set window boundaries
let start = 0;
let end = 0;
// initalize var to keep track of maximum length of substring without repeating characters.
let maxLen = 0;
// iterate throught the string from the 'end' pointer.
while(end < s.length) {
// check if the character at 's[end]' is not already in the set.
if(!charSet.has(s[end])){
// add the character to the set
charSet.add(s[end]);
// calculate the current substring length and update the 'maxLen'
maxLen = Math.max(maxLen, end - start + 1);
// move the 'end' pointer to expand the window
end++;
}else{
// if the character is already in the set, remove characters from 'start' until the duplicates are gone.
charSet.delete(s[start]);
// move the 'start' pointer to shrink the window
start++;
}
}
// Return the maximum length of the substring without repeating characters.
return maxLen;
};
// time complexity: O(n)
// space complexity: O(k)
Top comments (0)