The Sliding Window

The Sliding Window is a type of algorithm that helps us solve problems with fixed windows. It is used to optimize our programs, reducing the need for extra loops by reusing the result of the previous step in the next step. The brute-force approach to many problems that can be solved with this algorithm would be to use nested loops, which, generally speaking, should be avoided.

Leetcode Example

Leetcode Challenge: 1456. Maximum Number of Vowels in a Substring of Given Length

In this challenge, we are given a string s and an integer k, and asked to find a substring of length k such that it contains the most vowels out of any other substring of the same length. We must then return that number of vowels.

Some quick pseudo-code:

• We declare some variables: vowels to contain our vowels; window_start to represent the starting index of our window; num_vowels to contain an array of the number of vowels per substring; and current_vowels to keep track of how many vowels are in the current substring

• We iterate through the string, updating current_vowels as needed

• If the length of the window reaches k, we begin reducing current_vowels as needed (to ignore vowels outside the window) and increment window_start

• If the length of the window is k, we append the number of vowels in that substring to num_vowels

• After the loop is complete, we return the maximum value of the num_vowels array

See the image below for a visualization of how we'll be "sliding" through the input string! In this case, len(s) = 7 and k = 3. Every time we encounter a vowel, we increment current_vowels. Once we reach index 3, we first check if the value of s[window_start] is a vowel; if it is, we decrement current_vowels. Then, we increment the value of window_start.

See the code below for an implementation of this algorithm in Python!

class Solution:
    def maxVowels(self, s: str, k: int) -> int:

        vowels = 'aeiou'
        num_vowels = []
        window_start = 0
        current_vowels = 0

        for i in range(len(s)):
            if s[i] in vowels:
                current_vowels += 1
            if i >= k-1:
                num_vowels.append(current_vowels)
                if s[window_start] in vowels:
                    current_vowels -= 1
                window_start += 1
            i += 1

        return max(num_vowels)

I hope you found this helpful!