Maximum Vowels in a Substring: Sliding Window Pattern

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k. Vowels are a, e, i, o, and u.

This is LeetCode 1456: Maximum Number of Vowels in a Substring of Given Length, and it is a clean introduction to the fixed-size sliding window pattern.

Why this problem matters

Fixed-size sliding windows show up constantly in interview problems. You are given a window size k and asked to find the best (maximum, minimum, or some aggregate) value across all windows of that size. The trick is always the same: compute the answer for the first window, then update it incrementally as you slide one position at a time.

This problem is one of the simplest examples of that pattern. There is no variable window sizing, no shrinking logic, no complicated state. Just a count that goes up or down by one as you slide. If you can solve this, you have the foundation for every fixed-size window problem.

The key insight

You do not need to recount vowels from scratch for every window. When the window slides one position to the right, exactly one character leaves (the leftmost) and one character enters (the new rightmost). If the leaving character is a vowel, subtract one. If the entering character is a vowel, add one. That is the entire update.

This turns an O(n * k) brute force into O(n), because each slide costs O(1) instead of O(k).

The solution

def max_vowels(s: str, k: int) -> int:
    vowels = set("aeiou")
    count = sum(1 for c in s[:k] if c in vowels)
    max_count = count

    for i in range(k, len(s)):
        if s[i] in vowels:
            count += 1
        if s[i - k] in vowels:
            count -= 1
        max_count = max(max_count, count)

    return max_count

Here is what each piece does:

1. Build a vowel set for O(1) lookups. A set of five characters is effectively free.
2. Initialize the first window. Count how many of the first k characters are vowels. This is the baseline.
3. Slide the window. For each new position i, the character s[i] enters the window and the character s[i - k] leaves. Update the count accordingly.
4. Track the maximum. After each slide, compare the current count against the best seen so far.

Visual walkthrough

Let's trace through s = "abciiidef" with k = 3. Green cells are vowels inside the window, yellow cells are consonants inside the window, and red marks the character that just left.

The window slides across the string one character at a time. At position [3..5], the window contains "iii" with 3 vowels, which is the maximum. Every subsequent window has fewer vowels, so the answer is 3.

Complexity analysis

Time: O(n). We scan the first k characters once, then slide through the remaining n - k positions with O(1) work per slide.

Space: O(1). We only store two integers (count and max_count) and a fixed-size vowel set.

The building blocks

1. Fixed-size window initialization

Before you can slide, you need a valid starting window. Count the metric of interest (here, vowels) across the first k elements. This is the seed value that all subsequent slides build on.

count = sum(1 for c in s[:k] if c in vowels)
max_count = count

This same initialization pattern appears in every fixed-size window problem. In "Maximum Points You Can Obtain from Cards" you sum values. In "Find All Anagrams in a String" you build a frequency map. The structure is always the same: process the first k elements to create your initial state.

2. Slide and update pattern

Once initialized, the window slides by removing one element from the left and adding one on the right. The key insight is that you only update the metric based on these two elements, not the entire window.

for i in range(k, len(s)):
    if s[i] in vowels:       # entering character
        count += 1
    if s[i - k] in vowels:   # leaving character
        count -= 1
    max_count = max(max_count, count)

The leaving element is always at index i - k. This formula works because the window spans from i - k + 1 to i, so the element that just fell off is at i - k.

Edge cases

Before submitting, verify your solution handles:

• All vowels "aeiou" with k = 2: return 2. Every window is full of vowels.
• No vowels "bcdfg" with k = 3: return 0. Every window has zero vowels.
• k equals string length "abc" with k = 3: there is only one window, so return however many vowels are in the full string.
• k equals 1: each window is a single character. Return 1 if any vowel exists, 0 otherwise.
• String of length 1 "a" with k = 1: return 1.

The sliding window solution handles all of these without special cases, because the loop simply does not execute when there is only one window.

From understanding to recall

Reading through this solution takes a couple of minutes. Reproducing it from memory next week is a different challenge. The fixed-size window pattern has two moving pieces (initialize, then slide), and the slide step has two sub-pieces (remove leaving, add entering). Spaced repetition locks these pieces in by having you write the code at increasing intervals until it becomes automatic.

Related posts

• Longest Substring Without Repeating Characters - The classic variable-size sliding window problem
• Find All Anagrams in a String - Another fixed-size window with character counting
• Minimum Window Substring - The harder variable-size sliding window variant

Sliding window problems follow a small number of templates, and this one is the simplest. Once you have the fixed-size template down, the variable-size version is the next step. CodeBricks drills both templates as separate building blocks so you can assemble whichever one the problem calls for.