Sliding Window - Maximum Number of Vowels in a Substring of Given Length

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: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

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

Input: s = "cscode", k = 3
Output: 2
Explanation: "ode" contain 2 vowels.

Constraints:

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

Solution 1 - Using sliding window technique, keep track of maximum number of vowels found in a substring of length K

In this approach, we are going to apply sliding window technique using two pointers left and right, find the total number of vowels found in current window of length k, and keep track of maximum number of vowels found in all substrings of length k.

Implementation steps:

First, create four variables left, right that we will use to adjust the window, vowels to store total number of vowels found in current window, and maxVowels to hold the maximum vowels found so far in all substrings of length k.
Next, run a while loop until right pointer reaches end of string s, and do the following:
- Take the current character, and if that is a vowel, i.e. if the character is 'a', 'e', 'i', 'o', or 'u', then increment the count of vowels by 1.
- Next, check if we are going out of bounds of maximum substring length allowed k, that is right - left +1 > k then adjust the sliding window. Take the character at left pointer and increment left pointer, and if that is a vowel, then decrement the count of vowels by 1,
- Next, update the maxVowels with maximum value between vowels count in current window and the current maxVowels.
- At the end of while loop increment right pointer to move to the next element in string s.
Finally, return maxVowels.

public class MaximumNumberOfVowelsInSubstringOfGivenLength { static int maxVowels(String s, int k) { int left = 0; int right =0; int vowels = 0; int maxVowels = 0; while(right < s.length()) { char current = s.charAt(right); if(isVowel(current)) { vowels++; } while(right-left+1>k){ char leftChar = s.charAt(left); if(isVowel(leftChar)) { vowels--; } left++; } maxVowels = Math.max(maxVowels, vowels); right++; } return maxVowels; } static boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public static void main(String[] args) { System.out.println(maxVowels("abciiidef", 3)); System.out.println(maxVowels("aeiou", 2)); System.out.println(maxVowels("cscode", 3)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input string s.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: