Understanding the Sliding Window Technique

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:

• #3
• #209
• #53
• #1004
• #904

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)

References:

• LeetCode

• GG