Max Vowels Substring LeetCode 1456 Guide

LeetCode 1456 — Maximum Number of Vowels in a Substring of Given Length gives you a string s and an integer k. Your task is to return the maximum number of vowel letters in any substring of s that has length exactly k. Vowels are the characters a, e, i, o, and u.

The naive approach checks every substring of length k, counting vowels in each, at O(n*k) time. The optimal approach uses a fixed-size sliding window to compute the initial vowel count for the first k characters, then slides the window one step at a time, updating the count in O(1) per step for an overall O(n) solution with O(1) space.

This is a clean application of the fixed-window pattern. Because the window size never changes, you never need to expand or shrink it dynamically — just slide it one position at a time, adding the character entering from the right and removing the character leaving from the left.

Start by counting vowels in s[0..k-1], the first window. Call this count. Set maxVowels = count. Then slide the window one step to the right: the new right character is s[i] and the outgoing left character is s[i-k]. If s[i] is a vowel, increment count. If s[i-k] is a vowel, decrement count. Then update maxVowels = max(maxVowels, count).

This add-right subtract-left pattern is the defining characteristic of fixed-size sliding window. Because the window width is constant, each slide removes exactly one character from the left and adds exactly one from the right. The vowel count changes by at most +1 or -1 per step — no recomputation of the whole window is needed.

The window slides from i = k to i = n-1 (inclusive), giving n-k iterations after the initial setup. Together with the O(k) initialization, the total time is O(n). No extra array or hash map is needed — only two integer variables (count and maxVowels) and the vowel set, making space O(1).

The algorithm has two phases. Phase one initializes the count by scanning the first k characters. Phase two slides the window from position k to n-1, updating count with a single add and a single subtract per step. The maximum is tracked throughout both phases.

The loop index i represents the index of the new right character entering the window. The character leaving the window is always s[i-k], which is k positions behind the entering character. This ensures the window always spans exactly k characters: s[i-k+1..i].

Time complexity is O(n): the initialization loop runs k times and the sliding loop runs n-k times, summing to n. Space complexity is O(1): only count, maxVowels, and the vowel set (5 fixed elements) are used — no auxiliary arrays.

To check whether a character is a vowel in O(1), store the vowels in a set: {"a", "e", "i", "o", "u"}. In Python, a frozenset or set literal works. In Java, a HashSet<Character> or a string with contains() works. The set has exactly 5 elements and never changes, so its memory footprint is O(1).

An alternative is an if-chain: if c == "a" or c == "e" or c == "i" or c == "o" or c == "u". This works and is O(1), but the set is cleaner, easier to read, and less error-prone when transcribing. For Java, some prefer a boolean array of size 26 indexed by c - "a", which avoids boxing overhead.

A third alternative for Java is using String.indexOf: "aeiou".indexOf(c) >= 0. This scans a string of length 5 in O(5) = O(1) time and is very concise. All approaches are equivalent in asymptotic terms; the set or boolean array is generally preferred for clarity and direct intent.

Consider s = "abciiidef", k = 3. The string has 9 characters, so there are 9 - 3 + 1 = 7 windows of length 3. The expected answer is 3 (the window "iii" at positions 4-6).

Initialize on s[0..2] = "abc": a is a vowel (count=1), b is not, c is not. count = 1. maxVowels = 1. Now slide from i = 3 to i = 8.

i=3: right=s[3]="i" (vowel, count=2), left=s[0]="a" (vowel, count=1), max=1. i=4: right=s[4]="i" (vowel, count=2), left=s[1]="b" (not vowel), max=2. i=5: right=s[5]="i" (vowel, count=3), left=s[2]="c" (not vowel), max=3. i=6: right=s[6]="d" (not vowel), left=s[3]="i" (vowel, count=2), max=3. i=7: right=s[7]="e" (vowel, count=3), left=s[4]="i" (vowel, count=2), max=3. i=8: right=s[8]="f" (not vowel), left=s[5]="i" (vowel, count=1), max=3. Return 3.

Python: def maxVowels(s, k): vowels=set("aeiou"); count=sum(1 for c in s[:k] if c in vowels); maxV=count; for i in range(k, len(s)): count+=(s[i] in vowels)-(s[i-k] in vowels); maxV=max(maxV,count); if maxV==k: return k; return maxV. The boolean-to-int conversion (True=1, False=0) makes the add-right subtract-left a single expression. Early return when maxV == k is an optimization: k is the maximum possible vowel count in any window of length k.

Java: public int maxVowels(String s, int k) { Set<Character> vowels=new HashSet<>(Arrays.asList("a","e","i","o","u".toCharArray()... or use boolean[])); int count=0,maxV=0,n=s.length(); for(int i=0;i<k;i++) if(isVowel(s.charAt(i))) count++; maxV=count; for(int i=k;i<n;i++) { if(isVowel(s.charAt(i))) count++; if(isVowel(s.charAt(i-k))) count--; if(count>maxV) maxV=count; if(maxV==k) return k; } return maxV; }. The isVowel helper checks the boolean array vowel[c - "a"].

Both implementations run in O(n) time and O(1) space. The early-return when count == k skips unnecessary sliding once the theoretical maximum is reached. This optimization matters on inputs like "aaaa...a" where the maximum is found immediately after initialization.

LeetCode 1456 belongs to the fixed-size sliding window family. LeetCode 643 Maximum Average Subarray I is the closest relative — same structure, summing integers instead of counting characters. Both use the identical initialize-then-slide-with-add-right-subtract-left template.

LeetCode 438 Find All Anagrams in a String is a fixed-window problem that counts character frequencies using an array of size 26, sliding a window of length p.length() across s. LeetCode 1004 Max Consecutive Ones III is a variable-window problem (not fixed-size) but also counts a character property inside a window.

The fixed-window counting family includes any problem where window size is fixed and the answer is a maximum or minimum of a count or sum within that window. Once you recognize the template — initialize on first k, slide with add-right subtract-left, track max — each problem in the family reduces to a one-page solution.