Frontend School

Maximum Vowels in a Fixed-Length Substring

DSA
easy

Maximum Vowels in a Fixed-Length Substring

Easy
Sliding Window
String

Overview

In natural language processing, analyzing substrings for specific characteristics like vowel counts can be a preliminary step in text feature extraction. This problem challenges you to efficiently identify the substring of a given length that contains the highest number of vowels. Mastering this technique demonstrates a strong grasp of efficient string manipulation and the sliding window pattern, crucial for optimizing solutions in data processing.

What you need to do / Task

Implement a function maxVowels that takes a string s and an integer k as input. Your function should perform the following:

  1. Identify all vowel letters ('a', 'e', 'i', 'o', 'u') within the string s.
  2. Calculate the number of vowels in every contiguous substring of s that has a length exactly equal to k.
  3. Return the maximum number of vowels found among all such substrings.

Input & output

  • Input:
    • s: A string consisting of lowercase English letters.
    • k: An integer representing the required length of the substring.
  • Output:
    • An integer representing the maximum number of vowel letters found in any substring of s of length k.

Clarifications

  • Vowels are defined as 'a', 'e', 'i', 'o', 'u'. The input string s is guaranteed to contain only lowercase English letters, so case-insensitivity is not a concern.
  • The integer k will always be positive and will not exceed the length of the string s.

Examples

1

Example 1

Input:

s = "abciiidef", k = 3

Output:

3

Note:

The substring "iii" has 3 vowels. Other substrings like "abc" has 1 vowel, "bci" has 2, "cii" has 2, "iid" has 2, "ide" has 2, "def" has 1.

2

Example 2

Input:

s = "aeiou", k = 2

Output:

2

Note:

Any substring of length 2 will have 2 vowels, e.g., "ae", "ei", "io", "ou".

3

Example 3

Input:

s = "leetcode", k = 3

Output:

2

Note:

Substrings like "lee", "eet", "ode" all have 2 vowels. The maximum is 2.

Constraints

Constraints & assumptions

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

What interviewers evaluate

  • Correctness: The solution accurately identifies the maximum vowel count for all valid substrings.
  • Efficiency: The implementation achieves optimal time complexity, ideally linear (O(N)), and minimal space complexity (O(1)).
  • Clarity: The code is well-structured, easy to understand, and follows good programming practices.
  • Problem-solving: Demonstrates the ability to apply the sliding window technique effectively to string problems.

Loading editor...