[/dsa/leetcode]

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

Thursday, 17 September 2026

<medium> [problem]

Fixed size sliding window that counts vowels, updating the count by one character out and one character in at each step.

{string}{sliding window}

Problem

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Input: s = "abciiidef", k = 3
Output: 3
Explanation: the substring "iii" contains 3 vowel letters

Input: s = "aeiou", k = 2
Output: 2

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters
  • 1 <= k <= s.length

Approach

This is the same fixed size window as 643. Maximum Average Subarray I, but we count vowels instead of adding numbers.

Counting the vowels of every substring from scratch would be O(n * k). But two neighbouring windows share k - 1 characters, so when the window moves one step right only two things change:

  • the character that leaves on the left: if it’s a vowel, sum--
  • the character that enters on the right: if it’s a vowel, sum++

Count the vowels in the first window, then slide it to the end, keeping the largest count seen.

s = "abciiidef", k = 3
[abc]iiidef   first window          sum=1
a[bci]iidef   -a  +i                sum=1
ab[cii]idef   -b  +i                sum=2
abc[iii]def   -c  +i                sum=3   <- max
abci[iid]ef   -i  +d                sum=2
abcii[ide]f   -i  +e                sum=2
abciii[def]   -i  +f                sum=1
answer = 3
class Solution {
private:
    bool is(char c) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            return true;
        }
        return false;
    }

public:
    int maxVowels(string s, int k) {
        int sum = 0;
        const int n = s.size();
        for(int i = 0; i < k; i++) {
            if(is(s[i])) {
                sum++;
            }
        }
        int maxi = sum;
        for(int i = 1; i <= n - k; i++) {
            if(is(s[i - 1])) {
                sum--;
            }
            if(is(s[i + k - 1])) {
                sum++;
            }
            maxi = max(maxi, sum);
        }
        return maxi;
    }
};

Here i is where the window starts, so the character leaving is s[i - 1] and the one entering is s[i + k - 1].

  • time: O(n) - k steps for the first window, then one step per move
  • space: O(1) - two counters
quantinium © 2026