# 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](https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/?envType=study-plan-v2&envId=leetcode-75)

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`.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1698848728873/873ff2d8-f1c9-4ad9-a459-4869f19b6ce3.png align="center")

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

```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!