Densest Vowel Window
EasySliding WindowFree
Problem
A linguist is scanning a long lowercase transcript s for the passage of exactly k consecutive characters that is richest in vowels.
Return the largest number of vowels (a, e, i, o, u) found in any window of length k.
Example 1
- Input:
- s = "rhythmandblues", k = 4
- Output:
- 2
The window "blue" holds two vowels (u, e), and no window of length 4 holds three.
Example 2
- Input:
- s = "queueing", k = 3
- Output:
- 3
The window "ueu" is all vowels.
Constraints
- 1 ≤ k ≤ s.length ≤ 10^5
- s contains only lowercase English letters.
Hint
Show the first hint
Recounting every window from scratch repeats almost all the work.
Walkthrough
How to approach it
01Clarify before coding
- Is 'y' a vowel? No, only a, e, i, o, u.
- Can there be uppercase letters? No, lowercase only.
- Is k always at most the length of s? Yes.
02Brute force
For each start i, count the vowels in s[i..i+k-1] and keep the maximum.
Cost: O(n·k) time; with n = 10^5 and k = 5·10^4 that is about 2.5·10^9 character checks.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.