1456. Maximum Number of Vowels in a Substring of Given Length - Explanation

1. Brute Force

Intuition

The most straightforward approach is to check every possible substring of length k. For each starting position, count the vowels in the window and track the maximum count seen.

This works correctly but is inefficient because we recount characters for overlapping windows.

Algorithm

For each starting index i from 0 to n - k:
- Count the vowels in the substring s[i..i+k-1].
- Update the result if this count is larger.
Return the maximum vowel count found.

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowel = {'a', 'e', 'i', 'o', 'u'}
        res = 0

        for i in range(len(s) - k + 1):
            cnt = 0
            for j in range(i, i + k):
                cnt += 1 if s[j] in vowel else 0
            res = max(res, cnt)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Prefix Count

Intuition

We can precompute a prefix sum array where prefix[i] stores the number of vowels in s[0..i-1]. Then, the vowel count in any window s[i-k..i-1] is simply prefix[i] - prefix[i-k].

This allows us to answer each window query in O(1) time after O(n) preprocessing.

Algorithm

Build a prefix array where prefix[i+1] = prefix[i] + (1 if s[i] is a vowel else 0).
For each ending position i from k to n:
- Calculate the vowel count as prefix[i] - prefix[i-k].
- Update the maximum.
Return the maximum vowel count.

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowel = {'a', 'e', 'i', 'o', 'u'}
        prefix = [0] * (len(s) + 1)
        for i in range(len(s)):
            prefix[i + 1] = prefix[i] + (1 if s[i] in vowel else 0)

        res = 0
        for i in range(k, len(s) + 1):
            res = max(res, prefix[i] - prefix[i - k])

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sliding Window

Intuition

Instead of storing prefix sums, we can maintain a running count of vowels in the current window. As we slide the window right:

Add 1 if the new character entering the window is a vowel.
Subtract 1 if the character leaving the window is a vowel.

This gives us O(n) time with O(1) extra space.

Algorithm

Initialize a vowel count cnt and result res to 0.
Use two pointers: l (left) starts at 0, r (right) iterates through the string.
For each character at r:
- If it is a vowel, increment cnt.
- If the window size exceeds k, check if s[l] is a vowel and decrement cnt if so, then increment l.
- Update res with the maximum of res and cnt.
Return res.

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowel = {'a', 'e', 'i', 'o', 'u'}

        l = cnt = res = 0
        for r in range(len(s)):
            cnt += 1 if s[r] in vowel else 0
            if r - l + 1 > k:
                cnt -= 1 if s[l] in vowel else 0
                l += 1
            res = max(res, cnt)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

4. Sliding Window (Bit Mask)

Intuition

Checking if a character is a vowel using a set or string comparison can be optimized using a bitmask. We assign each letter a bit position (a=0, b=1, ..., z=25). The vowels form a constant bitmask. Checking if a character is a vowel becomes a single bitwise operation.

This is a micro-optimization but can improve cache performance and avoid hash lookups.

Algorithm

Create a bitmask with bits set for vowel positions: mask = (1 << 0) | (1 << 4) | (1 << 8) | (1 << 14) | (1 << 20) for a, e, i, o, u.
To check if character c is a vowel: (mask >> (c - 'a')) & 1.
Apply the same sliding window logic as before, using the bitmask for vowel checks.
Return the maximum vowel count.

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        def getId(c):
            return ord(c) - ord('a')

        mask = (1 << getId('a')) | (1 << getId('e')) | \
               (1 << getId('i')) | (1 << getId('o')) | \
               (1 << getId('u'))

        l = cnt = res = 0
        for r in range(len(s)):
            cnt += ((mask >> getId(s[r])) & 1)
            if r - l + 1 > k:
                cnt -= ((mask >> getId(s[l])) & 1)
                l += 1
            res = max(res, cnt)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Forgetting to Handle the Initial Window

A common mistake is updating the result before the window reaches size k. This can cause the algorithm to report incorrect maximum values from incomplete windows. Always ensure the window has exactly k elements before comparing with the result.

Not Removing the Outgoing Element Correctly

When sliding the window, forgetting to subtract the vowel count of the element leaving the window (at position l) leads to an ever-increasing count. The window must maintain exactly k elements, so when adding a new element on the right, the leftmost element must be removed from the count if the window exceeds size k.

Case Sensitivity with Vowels

If the input can contain uppercase letters, failing to handle case sensitivity causes vowels like 'A' or 'E' to be missed. Either convert the string to lowercase before processing or include both cases in the vowel set.