How do you solve Maximum Number of Vowels in a Substring of Given Length?

Use a sliding window of size k. Initialize pointers l and r to define the window boundaries. Maintain a running count of vowels in the current window. For each step, add the vowel contribution of the new character at r, and if the window size exceeds k, subtract the vowel contribution of the character at l and move l forward. Track the maximum vowel count seen during the process and return it at the end.

Maximum Number of Vowels in a Substring of Given Length

Q: What is the time complexity of Maximum Number of Vowels in a Substring of Given Length?

O(n). Each character is visited at most twice: once when entering the window and once when leaving it, resulting in a linear time complexity.

Q: What pattern does Maximum Number of Vowels in a Substring of Given Length use?

The Pattern: Sliding Window (Fixed-Size Window) The Heuristic: When asked to find a maximum or minimum value over all substrings or subarrays of fixed length, use a sliding window that updates state incrementally by adding the new element and removing the old, avoiding recomputation.

Medium Sliding Window

Problem

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters.
1 ≤ k ≤ s.length

Example

Input: s = "abciiidef", k = 3

Output: 3

The substring "iii" contains 3 vowels, which is the maximum possible for any substring of length 3. The algorithm uses a sliding window of size k to track the count of vowels in the current window. Starting with the first k characters, it counts vowels and then slides the window one character at a time, updating the count by removing the leftmost character and adding the new rightmost character. The maximum count encountered during this process is returned.

Approach

Straightforward Solution

A brute-force approach would check every substring of length k, counting vowels each time, resulting in O(n*k) time complexity, which is inefficient for large strings.

Core Observation

The problem requires finding the maximum number of vowels in any substring of fixed length k. This is a classic scenario for a sliding window approach, where the window size is fixed and the goal is to efficiently update the count as the window moves.

Path to Optimal

Preview

Recognizing that the window size is fixed allows the use of a sliding window that moves one character at a time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a sliding window of size k. Initialize pointers l and r to define the window boundaries…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character is visited at most twice: once when entering the window and once when leaving it, resulting in a linear time complexity.

Space

O(1)

Only a fixed-size set for vowels and a few integer variables are used, independent of input size.

Pattern Spotlight

Sliding Window (Fixed-Size Window)

When asked to find a maximum or minimum value over all substrings or subarrays of fixed length, use a sliding window that updates state incrementally by adding the new element and removing the old, avoiding recomputation.

Solution

Python

1class Solution:
  def maxVowels(self, s: str, k: int) -> int:
      vowels = set("aeiou")
      l = 0
      cur = 0
      ans = 0
7
      for r in range(len(s)):
          cur += s[r] in vowels
          if r - l + 1 > k:
              cur -= s[l] in vowels
              l += 1
          if r - l + 1 == k:
              ans = max(ans, cur)
15
      return ans

Step-by-Step Solution

Initialize Vowel Set and Sliding Window State

3vowels = set("aeiou")
4l = 0
5cur = 0
6ans = 0

Objective

To prepare the data structures and variables needed to track vowels and window boundaries.

Key Insight

Using a set for vowels allows O(1) membership checks, which is critical for efficient counting. Initializing the left pointer and counters sets the stage for the sliding window traversal, ensuring the algorithm can update counts incrementally as the window moves.

Interview Quick-Check

Core Logic

The vowel set enables constant-time checks to determine if a character is a vowel, which is essential for efficient counting.

State & Boundaries

Initialize the left pointer `l` at 0 and counters `cur` and `ans` at 0 to track the current vowel count and the maximum found.

Common Pitfalls & Bugs

Forgetting to initialize the maximum answer `ans` to zero can lead to incorrect results if all substrings have zero vowels.

Slide Window Across String and Update Vowel Counts

To iterate through the string with a right pointer, updating the vowel count for the current window and adjusting the left pointer to maintain window size k.

Return the Maximum Vowel Count Found

To output the maximum number of vowels found in any substring of length k after processing the entire string.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

cur += s[r] in vowels

Increment the current vowel count if the new character is a vowel.

Incrementing the count based on the new character's vowel status is the key incremental update that avoids recomputing the entire window's vowel count.

Line 11 Critical

cur -= s[l] in vowels

Decrement the current vowel count if the character leaving the window is a vowel.

Subtracting the vowel contribution of the character leaving the window is critical to maintain correctness while sliding the window efficiently.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does updating the vowel count incrementally as the window slides guarantee correctness and efficiency?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Maximum Number of Vowels in a Substring of Given Length from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Number of Vowels in a Substring of Given Length drill

or drill a free problem

1	`class Solution:`
2	`def maxVowels(self, s: str, k: int) -> int:`
3	`vowels = set("aeiou")`
4	`l = 0`
5	`cur = 0`
6	`ans = 0`
7
8	`for r in range(len(s)):`
9	`cur += s[r] in vowels`
10	`if r - l + 1 > k:`
11	`cur -= s[l] in vowels`
12	`l += 1`
13	`if r - l + 1 == k:`
14	`ans = max(ans, cur)`
15
16	`return ans`

3	`vowels = set("aeiou")`
4	`l = 0`
5	`cur = 0`
6	`ans = 0`