Maximum Number of Vowels in a Substring of Given Length - 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 & Output

Example 1 — Basic Case

$ Input: s = "abciio", k = 2

› Output: 2

💡 Note: The substring "ii" contains 2 vowels, and "io" contains 2 vowels. All substrings of length 2: "ab"=1, "bc"=0, "ci"=1, "ii"=2, "io"=2. Maximum is 2.

Example 2 — All Consonants

$ Input: s = "rhythms", k = 4

› Output: 0

💡 Note: No vowels in the string, so any substring of length 4 contains 0 vowels

Example 3 — All Vowels

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

› Output: 2

💡 Note: Any substring of length 2 contains exactly 2 vowels: "ae", "ei", "io", "ou" all have 2 vowels

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters
1 ≤ k ≤ s.length

Visualization

Tap to expand

Asked in

a Amazon 25 M Microsoft 18 G Google 15

The key insight is to use a sliding window approach to efficiently count vowels without redundant recalculations. Best approach is sliding window with Time: O(n), Space: O(1).

Common Approaches

✓ Brute Force

⏱️ Time: O(n×k) Space: O(1)

For each starting position, examine the k-character substring and count vowels. Keep track of the maximum count found.

Sliding Window

⏱️ Time: O(n) Space: O(1)

Count vowels in the first k characters, then slide the window by removing the leftmost character and adding the next character, updating the count incrementally.

Brute Force — Algorithm Steps

Step 1: Iterate through each possible starting position
Step 2: For each position, count vowels in the k-length substring
Step 3: Update maximum count if current count is higher

Visualization

Tap to expand

Step-by-Step Walkthrough

Position 0

Count vowels in first k characters

Position 1

Move to next position and recount

Continue

Repeat for all positions, track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int solution(char* s, int k) {
    int n = strlen(s);
    int maxVowels = 0;
    
    // Check every possible substring of length k
    for (int i = 0; i <= n - k; i++) {
        int currentVowels = 0;
        // Count vowels in current substring
        for (int j = i; j < i + k; j++) {
            if (isVowel(s[j])) {
                currentVowels++;
            }
        }
        if (currentVowels > maxVowels) {
            maxVowels = currentVowels;
        }
    }
    
    return maxVowels;
}

int main() {
    char s[100000];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×k)

For each of n-k+1 starting positions, we count k characters

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track counts and maximum

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler