Maximum Number of Vowels in a Substring of Given Length

Medium
242.

Maximum Number of Vowels in a Substring of Given Length

Maximum Number of Vowels in a Substring of Given Length is a medium coding problem on strings and sliding window, asked in Amazon, Google and Adobe interviews.

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

The vowel letters are a, e, i, o and u.

Example 1

Input
s = "abciiidef", k = 3
Output
3
Explanation
The substring "iii" holds three vowels.

Example 2

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

Example 3

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

Constraints

  • 1 <= s.length <= 40
  • 1 <= k <= s.length
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Vowels in a Substring of Given Length Solution

Maximum Number of Vowels in a Substring of Given Length solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Vowels in a Substring of Given Length is a medium coding problem on strings and sliding window, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Sliding Window
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

The vowel letters are a, e, i, o and u.

Example 1

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" holds three vowels.

Example 2

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

Example 3

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

Constraints

  • 1 <= s.length <= 40
  • 1 <= k <= s.length
  • s consists of lowercase English letters.

Hints for Maximum Number of Vowels in a Substring of Given Length

  1. Hint 1

    Recounting each window from scratch is O(n·k). The windows overlap heavily — reuse the count.

  2. Hint 2

    Slide by one: add the character entering on the right, remove the one leaving on the left.

  3. Hint 3

    Seed the count with the first k characters before the sliding loop starts.

How to solve Maximum Number of Vowels in a Substring of Given Length

Consecutive windows of length k differ by one character on each side, so maintain a single vowel count and adjust it as the window slides.

Approach

  1. Count the vowels in the first k characters and record it as the best.
  2. For each i from k onward, add 1 if s[i] is a vowel and subtract 1 if s[i - k] is a vowel.
  3. Update the best after each slide.

Why it works

The window [i-k+1, i] is the previous window plus s[i] minus s[i-k], so the two adjustments keep the count exact without rescanning. Every window is visited once.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Recounting each window is O(n·k).
  • Only lowercase vowels are in the alphabet here; no case handling is needed.

Reference solution

Python

def maxVowels(s: str, k: int) -> int:
    vowels = set("aeiou")
    cur = sum(1 for ch in s[:k] if ch in vowels)
    best = cur
    for i in range(k, len(s)):
        if s[i] in vowels:
            cur += 1
        if s[i - k] in vowels:
            cur -= 1
        if cur > best:
            best = cur
    return best

Java

public static int maxVowels(String s, int k) {
    String vowels = "aeiou";
    int cur = 0;
    for (int i = 0; i < k; i++) {
        if (vowels.indexOf(s.charAt(i)) >= 0) cur++;
    }
    int best = cur;
    for (int i = k; i < s.length(); i++) {
        if (vowels.indexOf(s.charAt(i)) >= 0) cur++;
        if (vowels.indexOf(s.charAt(i - k)) >= 0) cur--;
        if (cur > best) best = cur;
    }
    return best;
}

C++

int maxVowels(string s, int k) {
    string vowels = "aeiou";
    int cur = 0;
    for (int i = 0; i < k; i++) {
        if (vowels.find(s[i]) != string::npos) cur++;
    }
    int best = cur;
    for (int i = k; i < (int) s.size(); i++) {
        if (vowels.find(s[i]) != string::npos) cur++;
        if (vowels.find(s[i - k]) != string::npos) cur--;
        if (cur > best) best = cur;
    }
    return best;
}

JavaScript

var maxVowels = function(s, k) {
    const isV = function(c) { return "aeiou".indexOf(c) >= 0; };
    let cur = 0;
    for (let i = 0; i < k; i++) {
        if (isV(s[i])) cur++;
    }
    let best = cur;
    for (let i = k; i < s.length; i++) {
        if (isV(s[i])) cur++;
        if (isV(s[i - k])) cur--;
        if (cur > best) best = cur;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sliding Window Technique