Most vowels in any k letters
Given a lowercase string s and an integer k, return the largest number
of vowels (a, e, i, o, u) in any substring of
length k.
Examples
| Input | Output | Why |
|---|---|---|
s = "abciiidef", k = 3 | 3 | "iii". |
s = "aeiou", k = 2 | 2 | Every window is all vowels. |
s = "rhythm", k = 2 | 0 | No vowels at all. |
Constraints
- 1 ≤ k ≤ |s| ≤ 10⁵
- s is lowercase English letters
Hints
Hint 1
This is the running-sum window with a different quantity: count vowels instead of adding values.
Hint 2
When the window moves, only two letters change: the one entering and the one leaving.
Hint 3
The answer can never exceed k, so you may stop early once you reach it.
Where people lose marks
- Recounting the whole window at each step, which is O(nk).
- Checking the entering letter but forgetting to remove the leaving one.
Dry run on "abciiidef",3
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7sa0lob1c2hii3i4i5d6e7f8count1best1
The first window "abc" holds 1 vowel.
-
Step 2 / 7sa0b1loc2i3hii4i5d6e7f8count1best1
'i' enters (a vowel, +1), 'a' leaves (a vowel, −1). Count 1, best 1.
-
Step 3 / 7sa0b1c2loi3i4hii5d6e7f8count2best2
'i' enters (a vowel, +1), 'b' leaves (not a vowel). Count 2, best 2.
-
Step 4 / 7sa0b1c2i3loi4i5hid6e7f8count3best3
'i' enters (a vowel, +1), 'c' leaves (not a vowel). Count 3, best 3.
-
Step 5 / 7sa0b1c2i3i4loi5d6hie7f8count2best3
'd' enters (not a vowel), 'i' leaves (a vowel, −1). Count 2, best 3.
-
Step 6 / 7sa0b1c2i3i4i5lod6e7hif8count2best3
'e' enters (a vowel, +1), 'i' leaves (a vowel, −1). Count 2, best 3.
-
Step 7 / 7sa0b1c2i3i4i5d6loe7f8hicount1best3
'f' enters (not a vowel), 'i' leaves (a vowel, −1). Count 1, best 3.
How to think about it
Treat each letter as 1 if it is a vowel and 0 otherwise, and the question becomes the largest sum of k consecutive values. Count the vowels in the first k letters, then slide: add one if the entering letter is a vowel, subtract one if the leaving letter is.
Recognising that a count is just a sum of indicators is useful well beyond this problem. Any "most of X in a window of fixed length" question reduces to the same loop.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_vowels(s, k):
vowels = set("aeiou")
count = sum(c in vowels for c in s[:k]) # the first window
best = count
for i in range(k, len(s)):
count += (s[i] in vowels) - (s[i - k] in vowels)
best = max(best, count)
return best#include <string>
#include <algorithm>
static int isV(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }
int solve(const std::string& s, int k) {
int count = 0;
for (int i = 0; i < k; ++i) count += isV(s[i]); // the first window
int best = count;
for (int i = k; i < (int)s.size(); ++i) {
count += isV(s[i]) - isV(s[i - k]);
best = std::max(best, count);
}
return best;
}class Solution {
private int isV(char c) { return "aeiou".indexOf(c) >= 0 ? 1 : 0; }
public int maxVowels(String s, int k) {
int count = 0;
for (int i = 0; i < k; i++) count += isV(s.charAt(i)); // the first window
int best = count;
for (int i = k; i < s.length(); i++) {
count += isV(s.charAt(i)) - isV(s.charAt(i - k));
best = Math.max(best, count);
}
return best;
}
}function maxVowels(s, k) {
const isV = c => 'aeiou'.includes(c) ? 1 : 0;
let count = 0;
for (let i = 0; i < k; i++) count += isV(s[i]); // the first window
let best = count;
for (let i = k; i < s.length; i++) {
count += isV(s[i]) - isV(s[i - k]);
best = Math.max(best, count);
}
return best;
}fn solve(s: &str, k: usize) -> i32 {
let b = s.as_bytes();
let v = |c: u8| matches!(c, b'a' | b'e' | b'i' | b'o' | b'u') as i32;
let mut count: i32 = b[..k].iter().map(|&c| v(c)).sum(); // the first window
let mut best = count;
for i in k..b.len() {
count += v(b[i]) - v(b[i - k]);
best = best.max(count);
}
best
}-- Indicators of vowels, then the running window sum of width k.
solve :: String -> Int -> Int
solve s k = maximum (scanl step first (zip (drop k ind) ind))
where
ind = [if c `elem` "aeiou" then 1 else 0 | c <- s]
first = sum (take k ind)
step c (new, old) = c + new - old
Variants to try
- Return the substring: remember where the best window ends.
- Vowels have weights: replace the indicator with the weight; the loop does not change.
Next problems
Best total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem → Medium20 minEvery place an anagram begins
Compare a window's letter counts with a pattern's in O(1) per step by tracking how many letters still differ.
Open the problem → Medium15 minDistinct values in every window
Keep a count per value, not a set: a set cannot tell whether the value leaving still has a copy inside.
Open the problem →Write a solution and run it against the real test table.
Keep going
Best total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem → Medium20 minEvery place an anagram begins
Compare a window's letter counts with a pattern's in O(1) per step by tracking how many letters still differ.
Open the problem → Medium15 minDistinct values in every window
Keep a count per value, not a set: a set cannot tell whether the value leaving still has a copy inside.
Open the problem → Sliding windowThe pattern behind it
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.