Sliding Window with a Static Size

Let's use Maximum Number of Vowels in a Substring of Given Length as our example.

A brute-force approach would consist of checking every substring of size $k$ starting at each character of the string, which is $O(nk)$ time complexity, where $n$ is the length of the string and $k$ is the length of the substring.

However, we can easily notice that we have a lot of repeated work. In fact, what if we imagine to have a window of size k?

In this way, once we compute the window for the first time, we can simply shrink it from the left and expand it to the right by one. This -1 (shrinking) and +1 (expansion) would not change the size of the window, which will remain k.

The implementation would look something like:

class Solution:
    VOWELS = {"a", "e", "i", "o", "u"}

    def maxVowels(self, s: str, k: int) -> int:
        def is_vowel(char: str) -> bool:
            assert isinstance(char, str)
            assert len(char) == 1

            return char in Solution.VOWELS

        n = len(s)
        assert k <= n

        ans = 0
        for right in range(k):
            ans += int(is_vowel(s[right]))

        left = 0
        win_res = ans
        for right in range(right + 1, n):
            win_res -= int(is_vowel(s[left]))
            win_res += int(is_vowel(s[right]))

            left += 1
            ans = max(ans, win_res)

        return ans

Which has the following complexity:

• Time: $O(n)$
• Space: $O(1)$

Where n is the size of the string s.