Use the Sliding Window Pattern to Solve Problems in JavaScript

I’ve been spending a lot of time in the last few months refreshing my knowledge of algorithms and data structures. My day-to-day doesn’t involve a whole lot of algorithmic thinking, but it is a great way to fine-tune your problem solving skills. In this post I’ll talk about the sliding window pattern, and how it can be used to solve problems in JavaScript, using some common interview questions to demonstrate.

What is the Sliding Window Pattern?

In computer science, the sliding window technique is a widely used method for optimizing algorithms that process arrays or sequences of data, which often comes in the form of a string when presented as an interview question. The technique involves dividing the input data into overlapping or non-overlapping windows of a fixed size and processing each window individually. This can be especially useful for algorithms that perform operations such as searching, filtering, or aggregating data, as it allows us to make efficient use of limited resources, such as memory or processing power.

There are two important things to know about this pattern:

1. It is a derivative of the two-pointer pattern, where the left and right pointer is used to keep track of the current window.
2. A hash table is often the data structure of choice for keeping track of the data that is being iterated.

Why Use the Sliding Window Technique?

The sliding window technique is particularly useful for optimizing algorithms that have a time or space complexity that grows with the size of the input data. For example, an algorithm that needs to search for a pattern in a large text file could have a time complexity of O(n^2), where n is the size of the file. This would mean that the time taken by the algorithm to complete would grow quadratically with the size of the input. By using the sliding window technique, we can reduce the time complexity of the algorithm to O(n), which is much more efficient.

How to Implement the Sliding Window Technique in JavaScript?

Implementing the sliding window technique in JavaScript is straightforward and can be done using a loop and a queue or array data structure. Here is a very basic example of a sliding window implementation in JavaScript:

function slidingWindow(arr, windowSize) {
  let result = []
  let window = []

  for (let i = 0; i < arr.length; i++) {
    if (i >= windowSize) {
      result.push(window)
      window.shift()
    }
    window.push(arr[i])
  }
  result.push(window)

  return result
}

In this example, the function slidingWindow takes an array arr and a window size windowSize as input. The function uses a loop to iterate through the elements of the array and a queue (window) to store the current window. At each iteration, the function checks if the current index is greater than or equal to the window size. If it is, the current window is added to the result array and the first element of the window is removed using the shift method. This continues until all elements of the array have been processed.

A more common scenario is one where you have to figure out what window size should be, or where the window size may be variable. We’ll take a look at both of these scenarios, beginning with a common interview question that involves having to figure out what the size of the sliding window should be.

Problem 1: Find all Anagrams in a String

Problem Statement

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

Example 1
Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2
Input: s = “abab”, p = “ab”
Output: [0,1,2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Analysis

We know this is a sliding window problem because in order for a substring of s to be an anagram of p, the substring must match the length of p, thus defining the window size. We can also determine that we need to keep track of the characters that we need to form the anagram with a hash map because with a hash map data structure, we only care about the frequencey of each character in p, not the order. We can take this a step further by using this hash map as a sort of tally of characters that are needed to form the anagram in the current window by decrementing the count in the map as we encounter matching characters in the window from s.

Algorithm

Without looking at the solution, try using the steps below to solve the problem on LeetCode.

1. Initialize the output array that will be returned and a hash map to store the characters and their count from the anagram phrase (p), then populate the hashmap.
2. Create the left and right window pointers (both set to 0 because the right pointer will be gradually incrememnted until it reaches the size of p.length) and a variable to hold the count of characters needed to form an anagram, which we get from p.length. ie. the count is the total number of chars that are needed and that still haven’t been found.
3. Start sliding the window on s (ie. while (right < s.length))
   1. if the character at the right pointer index has a count greater than 0 in the map, decrement the count
   2. Next decrement the value in the neededChars map for the character that is currently at the right pointer of s and shift the right pointer + 1
   3. if the count is now 0, there is an anagram that begins at the left pointer, so push it into the output array
   4. Check if the window size is the same as p.length. If its the same, we’ll need to incremement the left pointer. But before we do that we need to do two things:
      1. Check if the char being left behind (the char at the left pointer) was a needed char, and if so, we’ll have to increment the total number of chars currently needed to form an anagram (ie. count++)
      2. Every time a needed char is left behind (outside the window) as the window moves forward to search the rest of the string, we need to increment that char’s value in the neededChars object (restore the need for that char for the window’s future reference). ie. (neededChars[s[left]]++)
      3. Now we increment the left pointer
4. return the result array

Notice in the following solution that we initialize both the left and right pointers to index 0. At first, the window will increase its length by taking steps forward with its right end. After the window size reaches the same length as p, the window will start inching forward like a caterpillar with the left end moving first.

Solution

function findAnagrams(s, p) {
  let result = []
  let neededChars = {}
  let count = p.length

  for (let char of p) {
    neededChars[char] = (neededChars[char] || 0) + 1
  }

  let left = 0
  let right = 0

  while (right < s.length) {
    if (neededChars[s[right]] > 0) {
      count--
    }
    neededChars[s[right]]--
    right++

    if (count === 0) {
      result.push(left)
    }

    if (right - left === p.length) {
      if (neededChars[s[left]] >= 0) {
        count++
      }
      neededChars[s[left]]++
      left++
    }
  }

  return result
}

Time Complexity: O(n) where n is the length of s Space Complexity: O(1) because the size of the neededChars object will never exceed 26 characters (the number of letters in the alphabet)

Problem 2: Longest Substring Without Repeating Characters

Problem Statement

Given a string, find the length of the longest substring without repeating characters.

Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.

Analysis

We can see that the problem involves finding the longest substring in a string that does not contain any repeating characters. We can use the sliding window technique to solve this problem by iterating through the string and keeping track of the characters that have already been seen. If we encounter a character that has already been seen, we can remove the first character of the substring (thus resizing the window) and continue checking the rest of the string.

There are some fundamentals truths about the problem that are important to recognize:

1. We can use the length of the window as the measure of the longest substring, continually updating the result as we iterate through the string. Whenever the current window length of non-repeating characters is greater than the longest window length we have seen thus far, we update the result.
2. We can use a hash table to keep track of the characters that have already been seen. This allows us to check if a character has already been seen in constant time.
3. While the more standard sliding window pattern typically has a start and end pointer (or left/right) like we saw in the preceeding problem, this variation of the pattern only has us keeping track of the current window start, where the end pointer is the index of the loop we use to iterate through the string.

Algorithm

Without looking at the solution, try using the steps below to solve the problem on LeetCode.

There are 5 things we need to keep track of:

• The current window start index
• The length of the current window
• The longest window length we have seen so far
• A hash table to keep track of the characters that have already been seen with the key as the character and the value as the index where the character was last seen
• The index of the current character we are looking at. This should be declared but not yet initialized, as the initial value will be set in the loop. However, we still want to be able to use it outside of the loop in case the longest window length ends at the very last index, so we declare it here.

1. Create the variables as described above.
2. Loop over the string
   1. Add the character and it’s index to the hashmap if it is not already there
      eg. if (!(char in lastSeenMap)) lastSeenMap[char] = i; where char = inputString[i]
   2. If the character is already in the hashmap, check if it appeared within the current window. i. If it has, we have to resize the window by setting the length of the current window to the i index minus the starting index of the current window. eg. currWindowLength = i - currWindowStart ii. The next thing we have to do is compare the new window length with the longest window length we’ve seen so far and if the current length is longer, then reset the longest seen so far to the current window length. iii. Next, set the current window’s starting index to the lastSeenMap[char] + 1 index. (The next substring will start after the last occurence of the current element)
   3. Update the last occurence of the element in the hash map (ie. lastSeenMap[char] = i
3. After the loop is completed, update the current window length and check if the longest/largest window is smaller than that of the current window length and update the longest window length accordingly.
4. Return the longest window length.

Solution

function lengthOfLongestSubstring(s) {
  let currWindowStart = 0,
    currWindowLength = 0,
    longestWindowLength = 0,
    lastSeenMap = {},
    index

  for (index = 0; index < s.length; index++) {
    let char = s[index]

    if (!(char in lastSeenMap)) lastSeenMap[char] = index
    else {
      if (lastSeenMap[char] >= currWindowStart) {
        currWindowLength = index - currWindowStart
        if (currWindowLength > longestWindowLength) {
          longestWindowLength = currWindowLength
        }
      }
      currWindowStart = lastSeenMap[char] + 1
    }
    lastSeenMap[char] = index
  }
  if (longestWindowLength < index - currWindowStart) {
    longestWindowLength = index - currWindowStart
  }

  return longestWindowLength
}

Problem 3: Longest Repeating Character Replacement

Problem Statement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.

Example 2:
Input: s = “AABABBA”, k = 1
Output: 4
Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.

Analysis

The problem description is a bit confusing at first, but the goal is to ultimately replace k letters with a different letter to try to create the longest possible repeating letter substring, then return the length of that substring. This problem has some similarities with the previous problem, but this one is agruably a bit easier.

Algorithm

Without looking at the solution, try using the steps below to solve the problem on LeetCode.

While this can be done with a hash map, when dealing with letters of the alphabet where you’re counting occurences of each letter, it can also be done by allocating an array of length 26 for each letter, and using the index to store the count at the position of that letter in the alphabet. That’s what we’ll do here. Additionally, we’ll use the end pointer of our sliding window as the index of the loop we iterate on the same way as we did in the previous problem.

1. Create map array of size 26 filled with 0’s
2. Initialize 3 variables:
   1. One to store the highest count of a letter we have seen in the current sliding window
   2. One to store the max window length that we have seen, which is based on having all matching characters (essentially the longest repeating character sequence we’ve seen so far)
   3. One to store the start index for the sliding window
3. Loop over the input string, where the index is the window’s end pointer
   1. Add 1 to the value at the character’s index in the array
   2. Set the high count by getting the max of either the current high count or the character we are currently iterating on
   3. If the size of the window minus the high count is greater than k, then we have to shrink the window by incrementing the start index because there are more characters in the current window than we can replace. HOWEVER, be sure to first decrement the value for the character at the start index in the map array
   4. Set the value for the max length of repeating character to either the max length seen so far or the current window length
4. return the max length

Solution

function characterReplacement(s, k) {
  let map = Array(26).fill(0),
    highCount = 0,
    maxLength = 0,
    start = 0

  for (let end = 0; end < s.length; end++) {
    let c = s[end]
    map[c] = (map[c] || 0) + 1

    highCount = Math.max(highCount, map[c])

    if (end - start + 1 - highCount > k) {
      map[s[start]]--
      start++
    }

    maxLength = Math.max(maxLength, end - start + 1)
  }
  return maxLength
}

Conclusion

The sliding window technique is a powerful optimization tool that can help to improve the efficiency of algorithms that process arrays or sequences of data. By dividing the input data into windows and processing each window individually, we can make efficient use of limited resources and reduce the time or space complexity of the algorithm.

In this post, we have discussed the sliding window technique and took a look at three example problems with different variations of the pattern. With this knowledge, you should be able to start using the sliding window technique when solving algorithm problems that can leverage this pattern.