MediumStringSliding Window

Maximum Number of Vowels in a Substring of Given Length

1 approach, code in every language

You are given a string s made of lowercase English letters and an integer k. A vowel is any of the characters 'a', 'e', 'i', 'o', or 'u'.

Consider every contiguous substring of s whose length is exactly k. Your task is to return the greatest number of vowels that appear in any single one of those substrings.

If no substring of length k exists, there is nothing to evaluate, but the constraints guarantee that k never exceeds the length of s.

Example 1

Input: s = "abciiidef", k = 3

Output: 3

The substring "iii" spans three positions and every character is a vowel, giving the maximum count of 3.

Example 2

Input: s = "aeiou", k = 2

Output: 2

Every window of length 2 is composed entirely of vowels, so the best any window can reach is 2.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters.
1 <= k <= s.length

Fixed-Size Sliding Window

Slide a window of width k across the string, updating the vowel count incrementally instead of recounting.

Loading animation…

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

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

Time

O(n)

Space

O(1)

Each character is added and removed from the window exactly once; the vowel lookup is constant time.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free