Maximum Number of Vowels in a Substring of Given Length

How it works

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.

Steps

1. 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.
2. To check if character c is a vowel: (mask >> (c - 'a')) & 1.
3. Apply the same sliding window logic as before, using the bitmask for vowel checks.
4. Return the maximum vowel count.

Complexity

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

Things to watch for

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.

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

class Solution {
public:
    int maxVowels(string s, int k) {
        int mask = (1 << ('a' - 'a')) | (1 << ('e' - 'a')) |
                   (1 << ('i' - 'a')) | (1 << ('o' - 'a')) |
                   (1 << ('u' - 'a'));

        int l = 0, cnt = 0, res = 0;
        for (int r = 0; r < s.size(); r++) {
            cnt += (mask >> (s[r] - 'a')) & 1;
            if (r - l + 1 > k) {
                cnt -= (mask >> (s[l] - 'a')) & 1;
                l++;
            }
            res = max(res, cnt);
        }

        return res;
    }
};