Maximum Number of Vowels in a Substring of Given Length

Problem

Given a lowercase string s and an integer k, look at every contiguous substring of s of length exactly k and return the largest number of vowels (a, e, i, o, u) any of them contains.

The answer is a count, not the substring itself. If s contains no vowels at all, the answer is 0.

Examples

• s = "abciiidef", k = 3 → 3 — the window "iii" is all vowels.
• s = "aeiou", k = 2 → 2 — every length-2 window ("ae", "ei", …) is two vowels.
• s = "rhythm", k = 4 → 0 — no vowels anywhere, so every window scores zero.

Constraints

• 1 <= len(s) <= 10^5
• 1 <= k <= len(s)
• s consists of lowercase English letters only.

Counting vowels from scratch in each of the n - k + 1 windows costs O(n·k) — up to ~10^9–10^10 checks. The expected solution updates the count in O(1) per slide.

Think about it first

TL;DR

Fixed-size sliding window with an incrementally maintained vowel count — O(n) time, O(1) space.

Approach 1 — Brute force

Count vowels independently in every length-k window.

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

Complexity: O(n·k) time, O(k) space for the slice. With n = 10^5 and large k, roughly 10^9–10^10 membership tests — over budget, and almost all of it is recounting characters the previous window already counted.

Approach 2 — Sliding window count

The insight: sliding a fixed window one step right changes its contents by exactly two characters — one in, one out. The vowel count therefore changes by at most 1 in each direction, so after an O(k) initialization every window is scored in O(1). (This is the general fixed-window rule: maintain the aggregate incrementally whenever the aggregate supports O(1) add/remove.)

def maxVowels(s: str, k: int) -> int:
    vowels = frozenset("aeiou")
    count = 0
    for ch in s[:k]:
        if ch in vowels:
            count += 1
    best = count
    for right in range(k, len(s)):
        if s[right] in vowels:           # entering character
            count += 1
        if s[right - k] in vowels:       # leaving character
            count -= 1
        best = max(best, count)
        if best == k:                    # optional early exit: cannot do better
            return best
    return best

Walkthrough on s = "abciiidef", k = 3:

best == k == 3 triggers the early exit; windows "iid", "ide", "def" are never scored. Answer: 3.

Complexity: O(n) time — one pass, O(1) work per character; O(1) space (the vowel set is constant-sized).

Common pitfalls

• Testing the wrong leaving index. When s[right] enters, s[right - k] leaves — not right - k + 1. Sanity-check with k = 1: entering and leaving indices must be right and right - 1.
• Rebuilding the count per window (calling a count over the slice inside the loop) silently reintroduces the O(n·k) cost even though the code “uses a window.”
• Fixed window means no shrink loop. If you’re writing while here, you’ve drifted into the variable-size template; this problem never asks whether the window is “valid” — every position is scored.
• Initializing best = 0 is fine here (counts are non-negative), but initialize from the first window’s count anyway — the habit saves you on problems where the aggregate can be negative.

Pattern takeaway

The fixed-size window template in three lines: build the first window’s aggregate in O(k), then slide with +entering / -leaving, tracking the best. Recognize it whenever the problem fixes the window length (substring of length k, k consecutive days) — the only design decision left is choosing an aggregate that updates in O(1), here a vowel counter.