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

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window Technique - The optimal solution maintains a fixed-size window that slides across the string
Hash Set / Set Operations - Used for O(1) vowel membership checking
Prefix Sum - An alternative approach uses cumulative sums to answer range queries efficiently
Bit Manipulation (optional) - Advanced optimization uses bitmasks for faster vowel checking

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

public class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        int res = 0;

        for (int i = 0; i <= s.length() - k; i++) {
            int cnt = 0;
            for (int j = i; j < i + k; j++) {
                if (vowels.contains(s.charAt(j))) {
                    cnt++;
                }
            }
            res = Math.max(res, cnt);
        }

        return res;
    }
}

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        int res = 0;

        for (int i = 0; i <= s.size() - k; i++) {
            int cnt = 0;
            for (int j = i; j < i + k; j++) {
                if (vowels.count(s[j])) {
                    cnt++;
                }
            }
            res = max(res, cnt);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    maxVowels(s, k) {
        const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
        let res = 0;

        for (let i = 0; i <= s.length - k; i++) {
            let cnt = 0;
            for (let j = i; j < i + k; j++) {
                if (vowels.has(s[j])) {
                    cnt++;
                }
            }
            res = Math.max(res, cnt);
        }

        return res;
    }
}

class Solution {
    fun maxVowels(s: String, k: Int): Int {
        val vowels = setOf('a', 'e', 'i', 'o', 'u')
        var res = 0

        for (i in 0..s.length - k) {
            var cnt = 0
            for (j in i until i + k) {
                if (s[j] in vowels) {
                    cnt++
                }
            }
            res = maxOf(res, cnt)
        }

        return res
    }
}

class Solution {
    func maxVowels(_ s: String, _ k: Int) -> Int {
        let vowels: Set<Character> = ["a", "e", "i", "o", "u"]
        let chars = Array(s)
        var res = 0

        for i in 0...(chars.count - k) {
            var cnt = 0
            for j in i..<(i + k) {
                if vowels.contains(chars[j]) {
                    cnt += 1
                }
            }
            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

public class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        int[] prefix = new int[s.length() + 1];

        for (int i = 0; i < s.length(); i++) {
            prefix[i + 1] = prefix[i] + (vowels.contains(s.charAt(i)) ? 1 : 0);
        }

        int res = 0;
        for (int i = k; i <= s.length(); i++) {
            res = Math.max(res, prefix[i] - prefix[i - k]);
        }

        return res;
    }
}

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        vector<int> prefix(s.size() + 1, 0);

        for (int i = 0; i < s.size(); i++) {
            prefix[i + 1] = prefix[i] + (vowels.count(s[i]) ? 1 : 0);
        }

        int res = 0;
        for (int i = k; i <= s.size(); i++) {
            res = max(res, prefix[i] - prefix[i - k]);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    maxVowels(s, k) {
        const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
        const prefix = new Array(s.length + 1).fill(0);

        for (let i = 0; i < s.length; i++) {
            prefix[i + 1] = prefix[i] + (vowels.has(s[i]) ? 1 : 0);
        }

        let res = 0;
        for (let i = k; i <= s.length; i++) {
            res = Math.max(res, prefix[i] - prefix[i - k]);
        }

        return res;
    }
}

class Solution {
    fun maxVowels(s: String, k: Int): Int {
        val vowels = setOf('a', 'e', 'i', 'o', 'u')
        val prefix = IntArray(s.length + 1)

        for (i in s.indices) {
            prefix[i + 1] = prefix[i] + if (s[i] in vowels) 1 else 0
        }

        var res = 0
        for (i in k..s.length) {
            res = maxOf(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

public class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

        int l = 0, cnt = 0, res = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt += (vowels.contains(s.charAt(r)) ? 1 : 0);
            if (r - l + 1 > k) {
                cnt -= (vowels.contains(s.charAt(l)) ? 1 : 0);
                l++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};

        int l = 0, cnt = 0, res = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt += (vowels.count(s[r]) ? 1 : 0);
            if (r - l + 1 > k) {
                cnt -= (vowels.count(s[l++]) ? 1 : 0);
            }
            res = max(res, cnt);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    maxVowels(s, k) {
        const vowels = new Set(['a', 'e', 'i', 'o', 'u']);

        let l = 0,
            cnt = 0,
            res = 0;
        for (let r = 0; r < s.length; r++) {
            cnt += vowels.has(s[r]) ? 1 : 0;
            if (r - l + 1 > k) {
                cnt -= vowels.has(s[l++]) ? 1 : 0;
            }
            res = Math.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

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    maxVowels(s, k) {
        const getId = (c) => {
            return c.charCodeAt(0) - 'a'.charCodeAt(0);
        };
        const mask =
            (1 << getId('a')) |
            (1 << getId('e')) |
            (1 << getId('i')) |
            (1 << getId('o')) |
            (1 << getId('u'));

        let l = 0,
            cnt = 0,
            res = 0;
        for (let r = 0; r < s.length; r++) {
            cnt += (mask >> getId(s.charAt(r))) & 1;
            if (r - l + 1 > k) {
                cnt -= (mask >> getId(s.charAt(l))) & 1;
                l++;
            }
            res = Math.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.