Maximum Number of Vowels in a Substring of Given Length Solution
Maximum Number of Vowels in a Substring of Given Length solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Vowels in a Substring of Given Length is a medium coding problem on strings and sliding window, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Strings, Sliding Window
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length exactly k.
The vowel letters are a, e, i, o and u.
Example 1
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" holds three vowels.
Example 2
Input: s = "aeiou", k = 2
Output: 2
Example 3
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" each contain two vowels.
Constraints
1 <= s.length <= 401 <= k <= s.lengths consists of lowercase English letters.
Hints for Maximum Number of Vowels in a Substring of Given Length
Hint 1
Recounting each window from scratch is O(n·k). The windows overlap heavily — reuse the count.
Hint 2
Slide by one: add the character entering on the right, remove the one leaving on the left.
Hint 3
Seed the count with the first
kcharacters before the sliding loop starts.
How to solve Maximum Number of Vowels in a Substring of Given Length
Consecutive windows of length k differ by one character on each side, so maintain a single vowel count and adjust it as the window slides.
Approach
- Count the vowels in the first
kcharacters and record it as the best. - For each
ifromkonward, add 1 ifs[i]is a vowel and subtract 1 ifs[i - k]is a vowel. - Update the best after each slide.
Why it works
The window [i-k+1, i] is the previous window plus s[i] minus s[i-k], so the two adjustments keep the count exact without rescanning. Every window is visited once.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Recounting each window is
O(n·k). - Only lowercase vowels are in the alphabet here; no case handling is needed.
Reference solution
Python
def maxVowels(s: str, k: int) -> int:
vowels = set("aeiou")
cur = sum(1 for ch in s[:k] if ch in vowels)
best = cur
for i in range(k, len(s)):
if s[i] in vowels:
cur += 1
if s[i - k] in vowels:
cur -= 1
if cur > best:
best = cur
return bestJava
public static int maxVowels(String s, int k) {
String vowels = "aeiou";
int cur = 0;
for (int i = 0; i < k; i++) {
if (vowels.indexOf(s.charAt(i)) >= 0) cur++;
}
int best = cur;
for (int i = k; i < s.length(); i++) {
if (vowels.indexOf(s.charAt(i)) >= 0) cur++;
if (vowels.indexOf(s.charAt(i - k)) >= 0) cur--;
if (cur > best) best = cur;
}
return best;
}C++
int maxVowels(string s, int k) {
string vowels = "aeiou";
int cur = 0;
for (int i = 0; i < k; i++) {
if (vowels.find(s[i]) != string::npos) cur++;
}
int best = cur;
for (int i = k; i < (int) s.size(); i++) {
if (vowels.find(s[i]) != string::npos) cur++;
if (vowels.find(s[i - k]) != string::npos) cur--;
if (cur > best) best = cur;
}
return best;
}JavaScript
var maxVowels = function(s, k) {
const isV = function(c) { return "aeiou".indexOf(c) >= 0; };
let cur = 0;
for (let i = 0; i < k; i++) {
if (isV(s[i])) cur++;
}
let best = cur;
for (let i = k; i < s.length; i++) {
if (isV(s[i])) cur++;
if (isV(s[i - k])) cur--;
if (cur > best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sliding Window Technique