AlgoMaster Logo

Maximum Number of Vowels in a Substring of Given Length

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to look at every substring of length exactly k in the string s and count how many vowels each one contains. Then we return the highest count we find.

A substring is a contiguous block of characters. So for s = "abciiidef" and k = 3, the substrings are: "abc", "bci", "cii", "iii", "iid", "ide", "def". We count the vowels in each and take the max.

Consecutive substrings of length k overlap heavily. Moving from one substring to the next loses one character on the left and gains one character on the right, while everything in between stays the same. Instead of recounting vowels from scratch every time, we can adjust the count using only the character we lost and the character we gained. That is the sliding window idea, and it turns a repetitive counting problem into a single pass over the string.

Key Constraints:

  • 1 <= s.length <= 10^5 → With n up to 100,000, we need O(n) or O(n log n). An O(n * k) approach where k is close to n would be O(n^2), which is too slow.
  • s consists of lowercase English letters → We only need to check if a character is one of 5 vowels. A set lookup or simple conditional works.
  • 1 <= k <= s.length → k is always valid. We don't need to handle k > s.length. But k could equal s.length, meaning there's only one substring to check.

Approach 1: Brute Force

Intuition

For every starting position, extract the substring of length k, count the vowels in it, and track the maximum. This mirrors how you would solve it by hand: pick a window, count the vowels, move to the next window, count again.

There are n - k + 1 substrings of length k, and counting vowels in each takes O(k) time, so the total work is O(n * k). When k is small this is fast, but when k is close to n it becomes O(n^2), which is too slow for n up to 100,000.

Algorithm

  1. Create a set of vowel characters for quick lookup.
  2. Initialize maxVowels = 0.
  3. For each starting index i from 0 to n - k:
    • Count the number of vowels in the substring from index i to i + k - 1.
    • Update maxVowels if this count is larger.
  4. Return maxVowels.

Visualization and Code

Loading animation...

This approach recounts the entire window from scratch each time. Consecutive windows share k-1 characters, so most of that counting is repeated. The next approach reuses the previous count and adjusts only for the two characters that change.

Approach 2: Sliding Window (Optimal)

Intuition

When the window slides one position to the right, the substring changes by exactly two characters: the character at the left edge drops out, and a new character at the right edge comes in. The k-1 characters in the middle stay the same.

If we already know how many vowels are in the current window, we can compute the vowel count for the next window in O(1). Check whether the outgoing character was a vowel (subtract 1 if so) and whether the incoming character is a vowel (add 1 if so).

The full algorithm becomes: count the vowels in the first window of size k, then slide across the string making O(1) adjustments at each step. This runs in O(n) time.

Algorithm

  1. Create a set of vowel characters for O(1) lookup.
  2. Count the vowels in the first window (indices 0 to k-1). Set this as both currentCount and maxVowels.
  3. Slide the window from index k to n-1:
    • If the character leaving the window (at index i - k) is a vowel, decrement currentCount.
    • If the character entering the window (at index i) is a vowel, increment currentCount.
    • Update maxVowels if currentCount is larger.
  4. Return maxVowels.

Visualization and Code

Loading animation...