DEV Community

Cover image for Understanding the Sliding Window Technique
Arpan Patel
Arpan Patel

Posted on

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 πŸ‘€:

window Sliding technique

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.

Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Enter fullscreen mode Exit fullscreen mode

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.

Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

References:

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (0)

Heroku

This site is powered by Heroku

Heroku was created by developers, for developers. Get started today and find out why Heroku has been the platform of choice for brands like DEV for over a decade.

Sign Up

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay