Maximum Number of Vowels in a Substring of Given Length — Editorial

Opening the reading…

Intuitionwhy neighboring windows differ by only two characters

A substring of length k is a window with exactly k positions. If you count its vowels directly, then move the window one position to the right, most of the characters are unchanged: only the old leftmost character leaves and one new character enters. The next vowel count is therefore the old count minus one possible vowel plus one possible vowel.

Start with the first k characters so the count is correct before any sliding begins. Then examine each following character as the new right edge. Remove the character k positions behind it, add the new character, and record the largest count seen. Every length-k substring becomes one of these windows, so the largest recorded count is the answer.

One update replaces exactly one character on each side of the fixed-size window.

Approach

Define a vowel test that returns true only for a, e, i, o, and u, because the problem's vowel set is fixed and every count update depends on this exact classification.

Count the vowels in the first k characters and store that count as the current window's value, because the sliding loop assumes the count already describes a complete window.

Set the maximum equal to the first window's count, because the first window is a valid candidate and must not be lost when later windows are compared.

For each index i from k through n - 1, inspect s[i - k] as the character leaving the window and decrement the count if it is a vowel, because retaining its contribution would count a character outside the new window.

Inspect s[i] as the entering character and increment the count if it is a vowel, because the new window ends at i and must include that character.

Update the maximum with the current count after both changes, because only then does the count represent the complete window from i - k + 1 through i.

Return the maximum after all right endpoints have been processed, because every possible length-k substring has appeared exactly once as a window.

Complexityone pass after one initial window

MEASURE	BOUND	WHY
Time	O(n)	The first window examines k characters and the sliding loop examines each of the remaining n - k characters once. Each position is classified by the vowel test at most when it enters and when it leaves, so the total work is proportional to n rather than to the number of possible windows times k.
Space	O(1) extra	The algorithm stores only the current count, the maximum, and a constant-size vowel predicate; the input string is not copied and the returned integer needs no output storage. The bound stays O(1) even for the worst input shape because the window size does not create an auxiliary structure.

Here n is the length of s. The output is one integer, so there is no output storage to exclude from the extra-space bound.

Annotated solutionC++ · fixed-size sliding window · complete judge-ready implementation

CPPCount the first window, then update its count by removing the outgoing character and adding the incoming character.

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    int maxVowels(string s, int k) {
        int n = static_cast<int>(s.size());
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };

        int count = 0;
        for (int i = 0; i < k; ++i) {
            if (isVowel(s[i])) {
                ++count;
            }
        }

        int maxCount = count;
        for (int i = k; i < n; ++i) {
            if (isVowel(s[i - k])) {
                --count;
            }
            if (isVowel(s[i])) {
                ++count;
            }
            maxCount = max(maxCount, count);
        }

        return maxCount;
    }
};

The index i names the character entering the window, so the character leaving is exactly k positions earlier at i - k. After the two conditional updates, the current window is s[i - k + 1] through s[i]. Keeping this relationship explicit is the key to avoiding rescans: the count always describes the same window that maxCount is comparing.