Sliding Window · Easy
Maximum Number of Vowels in a Substring of Length K
Solve it on DeVert Campus - free code runner
Problem
You are given a lowercase string s and an integer k. Find the maximum number of vowel characters ('a', 'e', 'i', 'o', 'u') contained in any substring of s of length exactly k.
Input and output
Input: The first line contains the string s. The second line contains the integer k.
Output: Print a single integer: the maximum number of vowels found in any substring of length k.
Example
Input: abciiidef 3 Output: 3
Constraints
1 <= k <= |s| <= 10^5
s consists only of lowercase English letters.
Key observation
Any 'count some property within a fixed-size window' problem (vowels here, but equally applicable to counting specific digits, characters, or conditions) follows this exact same incremental-update template - recognizing the template matters more than memorizing this specific instance.
Intuition
Find the maximum number of vowels contained in any substring of a fixed length k.
Brute force: Recount vowels in each window from scratch by scanning all k characters every time - this costs O(n*k), unnecessary when the count can be updated incrementally.
Optimised: Since only ONE character enters and ONE character leaves the window at each slide, updating a running vowel count by simply checking those two specific characters (rather than rescanning the whole window) achieves the same result in O(n) total instead of O(n*k).
Step by step
1. Count vowels in the FIRST window of length k.
2. Slide one character at a time: ADD 1 if the incoming character is a vowel, SUBTRACT 1 if the OUTGOING character was a vowel.
3. Track the maximum count seen across all window positions.
Complexity
Time: O(n) - one pass, with O(1) work per slide.
Space: O(1) - just a running vowel count and a running maximum.
Edge cases
Handle k = |s| (only one substring exists, the whole string) and strings with no vowels at all (the answer is 0). Also handle k = 1, where the answer is 1 if s contains any vowel, else 0.
Interview tip
Be ready to recognize this as the exact same fixed-size sliding window template as 'Maximum Sum Subarray of Size K' - just counting vowels instead of summing values, the underlying add-incoming/subtract-outgoing mechanism is identical.