LeetCode 1456 - Maximum Number of Vowels in a Substring of Given Length

LeetCode Problem 1456

Difficulty: 🟡 Medium
Topics: String, Sliding Window

Solution

Problem Understanding

This problem asks us to determine the maximum number of vowels that appear in any substring of a given length k within a string s. The input string s consists only of lowercase English letters, and k is guaranteed to be at least 1 and no larger than the length of the string. Vowels are defined as the characters 'a', 'e', 'i', 'o', and 'u'.

The expected output is a single integer representing the maximum number of vowels present in any contiguous substring of length k. For example, if s = "abciiidef" and k = 3, we must examine all substrings of length 3: "abc", "bci", "cii", "iii", "iid", "ide", "def", and find that "iii" contains the most vowels, which is 3.

The constraints indicate that s can be as long as 100,000 characters, so any algorithm with complexity higher than O(n) will likely be too slow. Edge cases include k = 1 where we only examine single characters, k = len(s) where the substring is the entire string, strings with no vowels, and strings made entirely of vowels.

Approaches

Brute Force

The brute-force approach involves generating all possible substrings of length k and counting the vowels in each substring. This works because it directly examines every candidate substring and compares vowel counts to find the maximum. However, for large strings, generating all substrings of length k and counting vowels for each results in O(n*k) time complexity, which is inefficient when n can be up to 100,000.

Optimal Approach - Sliding Window

The key insight is that the problem involves contiguous substrings of fixed length. This suggests a sliding window approach. Instead of recalculating the number of vowels for each substring from scratch, we can maintain a running count as the window moves:

1. Start with a window of size k at the beginning of the string and count its vowels.
2. Move the window one character to the right: subtract the contribution of the character leaving the window and add the contribution of the character entering.
3. Keep track of the maximum vowel count seen during this process.

This approach reduces the time complexity to O(n) since each character is processed at most twice (once entering the window, once leaving). Space complexity is O(1) since we only maintain a few counters.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*k)	O(1)	Count vowels in every substring of length k
Sliding Window	O(n)	O(1)	Maintain a running count as the window slides

Algorithm Walkthrough

1. Initialize a set containing all vowels for O(1) membership checking.
2. Initialize two counters: current_vowels for the number of vowels in the current window and max_vowels for the maximum observed.
3. Iterate over the first k characters and count the vowels. Set current_vowels to this value and also initialize max_vowels.
4. Slide the window through the string starting from index k to len(s) - 1.

a. If the character leaving the window (at index i - k) is a vowel, decrement current_vowels.

b. If the character entering the window (at index i) is a vowel, increment current_vowels.

c. Update max_vowels with the maximum of itself and current_vowels. 5. After processing all windows, return max_vowels.

Why it works: The sliding window guarantees that every substring of length k is considered exactly once. By incrementally updating the count, we avoid redundant computation while always maintaining the correct count of vowels in the current window.

Python Solution

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        current_vowels = sum(1 for c in s[:k] if c in vowels)
        max_vowels = current_vowels
        
        for i in range(k, len(s)):
            if s[i - k] in vowels:
                current_vowels -= 1
            if s[i] in vowels:
                current_vowels += 1
            max_vowels = max(max_vowels, current_vowels)
        
        return max_vowels

This implementation first calculates the number of vowels in the initial window of size k. It then iterates through the string, adjusting the count based on the characters leaving and entering the window. The max_vowels variable always contains the maximum observed vowel count.

Go Solution

func maxVowels(s string, k int) int {
    vowels := map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    currentVowels := 0
    
    for i := 0; i < k; i++ {
        if vowels[s[i]] {
            currentVowels++
        }
    }
    maxVowels := currentVowels
    
    for i := k; i < len(s); i++ {
        if vowels[s[i-k]] {
            currentVowels--
        }
        if vowels[s[i]] {
            currentVowels++
        }
        if currentVowels > maxVowels {
            maxVowels = currentVowels
        }
    }
    
    return maxVowels
}

The Go implementation mirrors Python. The differences include using a map for vowel lookup and explicit comparisons instead of a max function. Go slices handle character indexing similarly to Python strings.

Worked Examples

Example 1: s = "abciiidef", k = 3

Window	Leaving	Entering	current_vowels	max_vowels
"abc"	-	-	1	1
"bci"	a	i	1	1
"cii"	b	i	2	2
"iii"	c	i	3	3
"iid"	i	d	2	3
"ide"	i	e	2	3
"def"	i	f	1	3

Example 2: s = "aeiou", k = 2

Window	Leaving	Entering	current_vowels	max_vowels
"ae"	-	-	2	2
"ei"	a	i	2	2
"io"	e	o	2	2
"ou"	i	u	2	2

Example 3: s = "leetcode", k = 3

Window	Leaving	Entering	current_vowels	max_vowels
"lee"	-	-	2	2
"eet"	l	t	2	2
"etc"	e	c	1	2
"tco"	e	o	1	2
"cod"	t	d	1	2
"ode"	c	e	2	2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed at most twice: once entering and once leaving the sliding window.
Space	O(1)	Only a constant number of counters and a fixed-size set/map are used.

The algorithm scales linearly with the length of the string and does not require extra space proportional to n, making it efficient for the maximum input sizes.

Test Cases

# test cases
s = Solution()
assert s.maxVowels("abciiidef", 3) == 3  # substring "iii" has 3 vowels
assert s.maxVowels("aeiou", 2) == 2      # any substring of length 2 has 2 vowels
assert s.maxVowels("leetcode", 3) == 2   # substrings "lee", "eet", "ode" have 2 vowels
assert s.maxVowels("bcdfgh", 2) == 0     # no vowels in string
assert s.maxVowels("aaaaa", 5) == 5      # all vowels, window is full string
assert s.maxVowels("abcde", 1) == 1      # smallest window, check individual letters
assert s.maxVowels("abcde", 5) == 2      # full string, 2 vowels total

Test	Why
"abciiidef", k=3	Standard case with mixed vowels and consonants
"aeiou", k=2	All vowels, window smaller than string
"leetcode", k=3	Mixed letters, vowels dispersed
"bcdfgh", k=2	No vowels at all
"aaaaa", k=5	Entire string is vowels, edge case for max window
"abcde", k=1	Window size 1, tests minimal window