Shortest Valid Window | AlgoDrill Interview Course

Given a lowercase string s and a positive integer k, return the length of the shortest substring containing at least k vowels. Return 0 if no such substring exists.

Move right across the string and count the vowels in the current window. Once the count reaches k, the window is valid, but characters at the left edge may still be unnecessary. Record the current length, then move left forward while the window remains valid. If removing the leftmost character leaves at least k vowels, the next loop iteration records a shorter candidate. Once the vowel count falls below k, shrinking stops. The next iteration expands the window by moving right.

The condition requires a while loop because removing a consonant does not change the vowel count. Several characters may leave before the window becomes invalid. For a fixed right, the loop moves left until removing one more character makes the window invalid. The last valid length recorded is therefore the shortest valid window ending at right. Comparing those lengths across all right endpoints gives the shortest valid window in the string.

Find the shortest window containing two vowels

1 / 11

vowel_count: 0
best_length: not found
status: invalid

Start with left and right at index 0. The window "b" has no vowels, so expand right.

Why must the length be recorded before removing the leftmost character?

If no window ever reaches k vowels, best_length remains infinity and the function returns 0.

1def shortest_vowel_window(s: str, k: int) -> int:

2 vowels = set("aeiou")

3 left = 0

4 vowel_count = 0

5 best_length = float("inf")

7 for right, character in enumerate(s):

8 if character in vowels:

9 vowel_count += 1

11 while vowel_count >= k:

12 best_length = min(best_length, right - left + 1)

14 if s[left] in vowels:

15 vowel_count -= 1

16 left += 1

18 if best_length == float("inf"):

19 return 0

21 return best_length

Time: O(n)Space: O(1)

right visits each character once, and left removes each character at most once. The nested loop does not make the algorithm quadratic because both pointers move only forward. The vowel set has five entries, and the remaining state uses a fixed number of variables.