Maximum Number of Vowels in a Substring of Given Length

Intuition

Recounting the vowels inside every window of length k from scratch would repeat almost all of the work, because consecutive windows overlap in k - 1 characters. Instead we count the vowels of the very first window once, then move the window forward one step at a time. Each shift only changes two characters: a new character enters on the right and an old character leaves on the left. We add one when the incoming character is a vowel and subtract one when the outgoing character was a vowel. Tracking the running maximum of this count as we slide yields the answer in a single pass.

Algorithm walkthrough

1. 1Build the initial count by scanning the first k characters and counting how many are vowels; record this as the current best.
2. 2Move the window rightward: for each new index i from k to the end, look at the entering character s[i].
3. 3If s[i] is a vowel, increment the count; if the leaving character s[i - k] was a vowel, decrement the count.
4. 4After each adjustment the count exactly reflects the vowels inside the current window of length k.
5. 5Update best with the larger of best and the current count.
6. 6When the window has passed the end of the string, return best.

Implementation

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")
        count = sum(1 for c in s[:k] if c in vowels)
        best = count
        for i in range(k, len(s)):
            if s[i] in vowels:
                count += 1
            if s[i - k] in vowels:
                count -= 1
            best = max(best, count)
        return best