Maximum Number of Vowels in a Substring of Given Length (LC 1456)

Problem Statement#

LeetCode 1456 — Maximum Number of Vowels in a Substring of Given Length (Medium)

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', 'u'.

Constraints:

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

Input:  s = "abciiidef", k = 3
Output: 3
Explanation: "iii" has 3 vowels.

Input:  s = "leetcode", k = 3
Output: 2

Why This Problem Matters#

LC 1456 is the canonical fixed-size sliding window problem. It is the first problem interviewers use to test whether a candidate understands window mechanics: count a property over a fixed window of length k, slide one step right by adding the new right character and removing the old left character, and track the running maximum.

This problem appears in Amazon and Google phone screens as a warm-up. Solving it cleanly in O(n) with O(1) space signals that you understand sliding windows at the foundation level before tackling harder variable-window variants like LC 3, LC 424, or LC 76. The template here — initialise the first window, then slide — is the exact same template used in LC 643, LC 1343, and LC 1888.

The Core Insight#

Consecutive windows of length k overlap in k-1 characters. When the window slides one step right:

• One new character enters on the right (s[i])
• One old character leaves on the left (s[i-k])

So the vowel count changes by at most 1 in each direction. Maintain a running count and update it with a single addition and subtraction per step — O(1) per slide, O(n) overall.

The vowel set {'a','e','i','o','u'} supports O(1) membership testing, so each character check is constant time. Never recount from scratch.

Visual Dry Run#

Input: s = "abciiidef", k = 3

Answer: 3

Solution (Optimal)#

def maxVowels(s: str, k: int) -> int:
    vowels = set('aeiou')
 
    count = sum(1 for c in s[:k] if c in vowels)
    ans = count
 
    for i in range(k, len(s)):
        if s[i] in vowels:
            count += 1
        if s[i - k] in vowels:
            count -= 1
        ans = max(ans, count)
 
    return ans

var maxVowels = function(s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    let count = 0;
    for (let i = 0; i < k; i++) {
        if (vowels.has(s[i])) count++;
    }
    let ans = count;
 
    for (let i = k; i < s.length; i++) {
        if (vowels.has(s[i])) count++;
        if (vowels.has(s[i - k])) count--;
        ans = Math.max(ans, count);
    }
    return ans;
};

Time: O(n) — one pass for initial window O(k), one pass to slide O(n-k) Space: O(1) — only integer variables; vowel set is constant size

Common Mistakes#

• Recomputing the vowel count from scratch for every window — O(nk), TLE for large inputs
• Computing initial window inside the sliding loop without special-casing the first k elements — messy off-by-one
• Starting the slide loop at i = k - 1 and using s[i - k + 1] as outgoing — confusing; start at i = k and use s[i - k]
• Returning count instead of ans after the loop — count holds the last window only
• Using a list instead of a set for vowel membership — O(5) lookup is fine but a set is idiomatic

Interview Tips#

• Lead with the three-step template: (1) initialise first window, (2) slide and update, (3) track running max
• Mention that this template applies verbatim to any fixed-window problem — just change the metric
• If asked about k == len(s): one window, return its count; k == 1: check each character. Both handled correctly without special cases
• Early exit optimisation: if count == k, the entire window is vowels — return k immediately

Follow-up Questions#

• Multiple queries with different k: precompute a prefix sum of vowel indicators; vowel_count(l, r) = prefix[r+1] - prefix[l] in O(1) per query
• Return the actual window (not just count): track best_start when ans is updated; return s[best_start : best_start+k]
• Language-specific vowels: build the vowel set from the problem's definition; the algorithm is identical

Key Takeaways#

• Fixed-size sliding window template: initialise the first window, then slide right — add new right character, subtract departing left character, update running max
• The outgoing character when the right edge is at i is s[i - k]; start the slide loop at i = k
• Use a set for O(1) vowel membership; never recount the window from scratch
• Return ans (the running maximum) not count (the last window's value)
• Time O(n), space O(1) — this is the optimal solution; master this template for all fixed-window problems