Maximum Number of Vowels in a Substring of Given Length

MEDIUM

Description

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'.

Example 1:

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

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

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

Constraints:

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

Approaches

Checkout 2 different approaches to solve Maximum Number of Vowels in a Substring of Given Length. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Checking Every Substring

The most straightforward approach is to generate every possible substring of length k, count the number of vowels in each one, and keep track of the maximum count found.

Algorithm

Initialize a variable max_vowels to 0.
Iterate through the string s from index i = 0 to s.length() - k.
For each i, consider the substring of length k starting at i.
Initialize a current_vowels count to 0 for this substring.
Iterate from j = i to i + k - 1.
If the character at s.charAt(j) is a vowel, increment current_vowels.
After counting vowels for the current substring, update max_vowels = max(max_vowels, current_vowels).
After the outer loop finishes, return max_vowels.

This method involves a nested loop. The outer loop iterates through all possible starting positions of a substring of length k. The inner loop then iterates through each character of that substring to count the vowels.

class Solution {
    public int maxVowels(String s, int k) {
        int maxVowels = 0;
        // Outer loop for all possible start indices of a substring of length k
        for (int i = 0; i <= s.length() - k; i++) {
            int currentVowels = 0;
            // Inner loop to count vowels in the current substring
            for (int j = i; j < i + k; j++) {
                if (isVowel(s.charAt(j))) {
                    currentVowels++;
                }
            }
            maxVowels = Math.max(maxVowels, currentVowels);
        }
        return maxVowels;
    }

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

While simple, this approach is inefficient because it repeatedly scans overlapping portions of the string.

Complexity Analysis

Time Complexity: O(N * K), where N is the length of the string `s`. We iterate through `N - K + 1` possible starting positions for the substring. For each substring, we iterate `K` times to count the vowels. This results in a nested loop structure, leading to a time complexity that can be approximated as O(N * K).Space Complexity: O(1). We only use a few variables to store the maximum count and the current count, which does not depend on the input size.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient for large inputs, as it re-calculates the vowel count for overlapping parts of substrings repeatedly.
Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Maximum Number of Vowels in a Substring of Given Length. Click on different languages to view the code.

class Solution {
public
  int maxVowels(String s, int k) {
    int t = 0, n = s.length();
    for (int i = 0; i < k; ++i) {
      if (isVowel(s.charAt(i))) {
        ++t;
      }
    }
    int ans = t;
    for (int i = k; i < n; ++i) {
      if (isVowel(s.charAt(i))) {
        ++t;
      }
      if (isVowel(s.charAt(i - k))) {
        --t;
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
private
  boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
}

Video Solution

Watch the video walkthrough for Maximum Number of Vowels in a Substring of Given Length

Patterns:

Sliding Window

Data Structures:

String

Companies:

Turing |Wayfair |