Maximum Number of Vowels in a Substring of Given Length solution and explanation
TCS
Google
9 more videos on this problem
Maximum Number of Vowels in a Substring of Given Length - Leetcode 1456 - PythonNeetCodeIO · 7:58 · 21K views
Maximum Number of Vowels in a Substring of Given Length | MICROSOFT | Leetcode - 1456 | Live CodingcodestorywithMIK · 13:01 · 14K views
Maximum Vowels in a Substring (LeetCode 1456) | Full solution with animations | Sliding WindowNikhil Lohia · 13:12 · 12K views
LeetCode Problem 1456: Solve the 'Maximum Number of Vowels in a Substring of Given Length'Engineering Digest · 7:32 · 5K views
Maximum Number of Vowels in a Substring of Given Length - LeetCode 1456 - Python #leetcode75Deepti Talesra · 7:12 · 3K views
Maximum Number of Vowels in a Substring of Given Length || Sliding Window || Leetcode 1456Aryan Mittal · 11:41 · 2K views
Maximum Number of Vowels in a Substring of Given Length (Leetcode 1456)Coding Interviews · 15:07 · 902 views
1456. Maximum Number of Vowels in a Substring of Given Length (Leetcode Medium)Programming Live with Larry · 5:35 · 623 views
1456. Maximum Number of Vowels in a Substring of Given Length | Sliding Window | LeetCode DailyDeep Tech · 9:37 · 607 views
Maximum Number of Vowels in a Substring of Given Length - LeetCode 1456 - Python SolutionCode with Carter · 9:20 · 559 views
The problem
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
Example 1:
Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii" contains 3 vowel letters.
Example 2:
Input: s = "aeiou", k = 2 Output: 2 Explanation: Any substring of length 2 contains 2 vowels.
Example 3:
Input: s = "leetcode", k = 3 Output: 2 Explanation: "lee", "eet" and "ode" contain 2 vowels.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.1 <= k <= s.length
Approach overview
Problem Overview: Given a string s and an integer k, find the maximum number of vowels present in any substring of length k. You must examine all substrings of fixed size k and return the highest vowel count among them.
Approach 1: Sliding Window (O(n) time, O(1) space)
The key observation is that every candidate substring has the same length k. Instead of recomputing the vowel count for every substring from scratch, maintain a running count while moving a window across the string. Start by counting vowels in the first k characters. Then iterate through the string one character at a time: remove the effect of the character leaving the window and add the effect of the character entering it. This constant-time update makes each step efficient. Track the maximum count seen so far while iterating.
This approach processes each character once, resulting in O(n) time complexity and O(1) space since only a few counters are stored. The technique is a classic example of the sliding window pattern used in many string problems involving fixed-size subarrays or substrings.
Approach 2: Prefix Sum + Binary Search Style Range Query (O(n) preprocessing, O(1) query, O(n) space)
Another method precomputes a prefix array where prefix[i] stores the number of vowels in the first i characters of the string. With this structure, the number of vowels in any substring [l, r] can be calculated instantly as prefix[r + 1] - prefix[l]. Iterate through all starting positions of length k substrings and compute the vowel count using the prefix array. Each query becomes constant time after preprocessing.
This method uses O(n) extra space for the prefix array but keeps the logic straightforward and useful when you need repeated substring range queries. The technique is based on the prefix sum pattern often used for fast range calculations.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see that you recognize fixed-size substring problems and apply the sliding window pattern to avoid redundant computation. A brute-force solution that recalculates each substring demonstrates basic understanding, but the sliding window shows algorithmic maturity and reduces time complexity from O(n * k) to O(n).
Approach 1: Sliding Window Approach
This approach uses the sliding window technique to efficiently find the maximum number of vowels in any substring of length k.
We first calculate the number of vowels in the initial window of length k. Then, for each subsequent character, we slide the window by one character to the right: we remove the character that goes out of the window and add the one that comes into the window, updating our vowel count accordingly.
This ensures that we examine each character in the string only once, leading to an O(n) time complexity.
def maxVowels(s: str, k: int) -> int:
vowels = set('aeiou')
max_count = current_count = sum(1 for char in s[:k] if char in vowels)
for i in range(k, len(s)):
current_count += s[i] in vowels
current_count -= s[i-k] in vowels
max_count = max(max_count, current_count)
return max_count
# Example usage
print(maxVowels("abciiidef", 3))public class MaxVowels {
private boolean isVowel(char ch) {
return "aeiou".indexOf(ch) != -1;
}
public int maxVowels(String s, int k) {
int maxCount = 0, currentCount = 0;
for (int i = 0; i < k; i++) {
if (isVowel(s.charAt(i))) {
currentCount++;
}
}
maxCount = currentCount;
for (int i = k; i < s.length(); i++) {
if (isVowel(s.charAt(i))) {
currentCount++;
}
if (isVowel(s.charAt(i - k))) {
currentCount--;
}
maxCount = Math.max(maxCount, currentCount);
}
return maxCount;
}
public static void main(String[] args) {
MaxVowels mv = new MaxVowels();
System.out.println(mv.maxVowels("abciiidef", 3));
}
}#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isVowel(char ch) {
static unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
return vowels.count(ch) > 0;
}
int maxVowels(const string &s, int k) {
int maxCount = 0, currentCount = 0;
int n = s.size();
for (int i = 0; i < k; ++i) {
if (isVowel(s[i])) {
++currentCount;
}
}
maxCount = currentCount;
for (int i = k; i < n; ++i) {
currentCount += isVowel(s[i]) - isVowel(s[i - k]);
maxCount = max(maxCount, currentCount);
}
return maxCount;
}
int main() {
string s = "abciiidef";
int k = 3;
cout << maxVowels(s, k) << endl;
return 0;
}function maxVowels(s, k) {
const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
let maxCount = 0, currentCount = 0;
for (let i = 0; i < k; ++i) {
if (vowels.has(s[i])) {
currentCount++;
}
}
maxCount = currentCount;
for (let i = k; i < s.length; ++i) {
if (vowels.has(s[i])) {
currentCount++;
}
if (vowels.has(s[i - k])) {
currentCount--;
}
maxCount = Math.max(maxCount, currentCount);
}
return maxCount;
}
// Example usage
console.log(maxVowels("abciiidef", 3));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int maxVowels(char * s, int k) {
int maxCount = 0, currentCount = 0;
int length = strlen(s);
for (int i = 0; i < k; i++) {
if (isVowel(s[i])) {
currentCount++;
}
}
maxCount = currentCount;
for (int i = k; i < length; i++) {
if (isVowel(s[i])) {
currentCount++;
}
if (isVowel(s[i - k])) {
currentCount--;
}
if (currentCount > maxCount) {
maxCount = currentCount;
}
}
return maxCount;
}
int main() {
char s[] = "abciiidef";
int k = 3;
printf("%d\n", maxVowels(s, k));
return 0;
}using System;
public class MaxVowelsSolution {
public int MaxVowels(string s, int k) {
string vowels = "aeiou";
int maxCount = 0, currentCount = 0;
for (int i = 0; i < k; i++) {
if (vowels.IndexOf(s[i]) >= 0) {
currentCount++;
}
}
maxCount = currentCount;
for (int i = k; i < s.Length; i++) {
if (vowels.IndexOf(s[i]) >= 0) {
currentCount++;
}
if (vowels.IndexOf(s[i - k]) >= 0) {
currentCount--;
}
maxCount = Math.Max(maxCount, currentCount);
}
return maxCount;
}
public static void Main(string[] args) {
var solution = new MaxVowelsSolution();
Console.WriteLine(solution.MaxVowels("abciiidef", 3));
}
}Python's set data structure aids rapid lookup of vowels. The code calculates initial vowel counts and then iterates over the rest of the string. For each position, we adjust current_count for the character added to the window and the one removed from it, updating max_count appropriately to reflect the highest vowel count seen in a window.
Time Complexity: O(n), one pass over the string.
Space Complexity: O(1), with a constant size set for vowels.
Approach 2: Prefix Sum and Binary Search Approach
Another way to tackle this problem is to use a combination of prefix sums and binary search to precompute regions of vowels.
First, we establish a prefix sum array that accumulates the number of vowels encountered at each character index in the string. Then, we use a binary search within this prefix sum to efficiently find the maximum number of vowels in any moving window of length k.
This approach is more complex and is generally less optimal than the sliding window approach but provides an alternative methodology.
def maxVowels(s: str, k: int) -> int:
n = len(s)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + (s[i] in 'aeiou')
max_count = 0
for i in range(k, n + 1):
max_count = max(max_count, prefix[i] - prefix[i - k])
return max_count
# Example usage
print(maxVowels("abciiidef", 3))public class MaxVowels {
public int maxVowels(String s, int k) {
int n = s.length();
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + ("aeiou".indexOf(s.charAt(i)) >= 0 ? 1 : 0);
}
int maxCount = 0;
for (int i = k; i <= n; i++) {
maxCount = Math.max(maxCount, prefix[i] - prefix[i - k]);
}
return maxCount;
}
public static void main(String[] args) {
MaxVowels mv = new MaxVowels();
System.out.println(mv.maxVowels("abciiidef", 3));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int maxVowels(const string &s, int k) {
int n = s.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + isVowel(s[i]);
}
int maxCount = 0;
for (int i = k; i <= n; ++i) {
maxCount = max(maxCount, prefix[i] - prefix[i - k]);
}
return maxCount;
}
int main() {
cout << maxVowels("abciiidef", 3) << endl;
return 0;
}function maxVowels(s, k) {
let n = s.length;
let prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + ('aeiou'.includes(s[i]) ? 1 : 0);
}
let maxCount = 0;
for (let i = k; i <= n; i++) {
maxCount = Math.max(maxCount, prefix[i] - prefix[i - k]);
}
return maxCount;
}
// Example usage
console.log(maxVowels("abciiidef", 3));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int maxVowels(char * s, int k) {
int length = strlen(s);
int prefix[length + 1];
prefix[0] = 0;
for (int i = 0; i < length; ++i) {
prefix[i + 1] = prefix[i] + isVowel(s[i]);
}
int maxCount = 0;
for (int i = k; i <= length; ++i) {
maxCount = prefix[i] - prefix[i - k] > maxCount ? prefix[i] - prefix[i - k] : maxCount;
}
return maxCount;
}
int main() {
char s[] = "abciiidef";
int k = 3;
printf("%d\n", maxVowels(s, k));
return 0;
}using System;
public class MaxVowelsSolution {
public int MaxVowels(string s, int k) {
int n = s.Length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + ("aeiou".IndexOf(s[i]) >= 0 ? 1 : 0);
}
int maxCount = 0;
for (int i = k; i <= n; i++) {
maxCount = Math.Max(maxCount, prefix[i] - prefix[i - k]);
}
return maxCount;
}
public static void Main(string[] args) {
var solution = new MaxVowelsSolution();
Console.WriteLine(solution.MaxVowels("abciiidef", 3));
}
}The Python solution constructs a prefix sum array to accumulate counts of vowels. The maximum number of vowels in any k-length substring is determined from differences in prefix sums separated by k, using these differences to represent vowel counts within any window.
Time Complexity: O(n), for calculating the prefix sums and finding the maximum count.
Space Complexity: O(n), for the prefix array.
Approach 3: Sliding Window
First, we count the number of vowels in the first k characters, denoted as cnt, and initialize the answer ans as cnt.
Then we start traversing the string from k. For each iteration, we add the current character to the window. If the current character is a vowel, we increment cnt. We remove the first character from the window. If the removed character is a vowel, we decrement cnt. Then, we update the answer ans = max(ans, cnt).
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function maxVowels(s: string, k: number): number {
const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
let cnt = 0;
for (let i = 0; i < k; i++) {
if (vowels.has(s[i])) {
cnt++;
}
}
let ans = cnt;
for (let i = k; i < s.length; i++) {
if (vowels.has(s[i])) {
cnt++;
}
if (vowels.has(s[i - k])) {
cnt--;
}
ans = Math.max(ans, cnt);
}
return ans;
}func maxVowels(s string, k int) int {
isVowel := func(c byte) bool {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}
cnt := 0
for i := 0; i < k; i++ {
if isVowel(s[i]) {
cnt++
}
}
ans := cnt
for i := k; i < len(s); i++ {
if isVowel(s[i-k]) {
cnt--
}
if isVowel(s[i]) {
cnt++
}
ans = max(ans, cnt)
}
return ans
}class Solution {
/**
* @param String $s
* @param Integer $k
* @return Integer
*/
function isVowel($c) {
return $c === 'a' || $c === 'e' || $c === 'i' || $c === 'o' || $c === 'u';
}
function maxVowels($s, $k) {
$cnt = 0;
for ($i = 0; $i < $k; $i++) {
if ($this->isVowel($s[$i])) {
$cnt++;
}
}
$ans = $cnt;
for ($j = $k; $j < strlen($s); $j++) {
if ($this->isVowel($s[$j - $k])) {
$cnt--;
}
if ($this->isVowel($s[$j])) {
$cnt++;
}
$ans = max($ans, $cnt);
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), one pass over the string. |
| Prefix Sum and Binary Search Approach | Time Complexity: O(n), for calculating the prefix sums and finding the maximum count. |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution for fixed-length substring problems and expected interview answer |
| Prefix Sum | O(n) | O(n) | Useful when many substring range queries are required after preprocessing |
Frequently asked questions
Is Maximum Number of Vowels in a Substring of Given Length easy or hard?
The problem is generally classified as Medium. The implementation is straightforward once you recognize the sliding window pattern, but candidates who try brute force substring checks may end up with inefficient O(n * k) solutions.
Maximum Number of Vowels in a Substring of Given Length Python/Java solution
In Python or Java, implement a sliding window that iterates through the string once. Maintain a vowel count for the current window and update it when the window shifts. This approach works in O(n) time and O(1) space and is commonly used in competitive programming and interviews.
How to solve Maximum Number of Vowels in a Substring of Given Length in O(n)?
Use a sliding window of size k. Count vowels in the first k characters, then move the window one step at a time. Decrease the count if the left character was a vowel and increase it if the new right character is a vowel. Track the maximum value during traversal.
What is the best approach for Maximum Number of Vowels in a Substring of Given Length?
The sliding window approach is the best solution. It maintains a running count of vowels while moving a fixed-size window of length k across the string. Each step updates the count by removing the outgoing character and adding the incoming one, resulting in O(n) time and O(1) space.
Is Maximum Number of Vowels in a Substring of Given Length asked at Google/Amazon/Meta?
Sliding window string problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests pattern recognition, efficient substring processing, and understanding of fixed-length window optimization.
What data structure is used in Maximum Number of Vowels in a Substring of Given Length?
The problem mainly relies on the sliding window technique and simple character checks. Many implementations use a set or conditional checks to determine if a character is a vowel, while maintaining a running counter for the window.
What is the time complexity of Maximum Number of Vowels in a Substring of Given Length?
The optimal sliding window solution runs in O(n) time where n is the length of the string, because each character is processed once as the window moves forward. Space complexity is O(1) since only counters and a small vowel check structure are required.