Question - 27:

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

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.

Approach taken:

class Solution {
    public int maxVowels(String s, int k) {
        int max = 0;
        int count = 0;
        for(int i=0 ; i<k ;i++){
            if(String.valueOf(s.charAt(i)).matches("[aeiou]"))
              count++;
        }
        max = count;
        for(int i=k ; i< s.length() ;i++){
            int isVowel=0;
            if(String.valueOf(s.charAt(i-k)).matches("[aeiou]"))
               count--;
            if(String.valueOf(s.charAt(i)).matches("[aeiou]"))  
               count++;

            max=Math.max(max,count);  
        }
    return max;    
    }
}

Step-by-step implementation:

1. The method takes two parameters, a string s and an integer k.

2. The method declares two integer variables, max and count, and initializes them both to 0.

3. The method then enters a for loop that runs from 0 to k - 1. This loop counts the number of vowels in the first k characters of the string s.

4. The method updates the max variable to be equal to count.

5. The method enters another for loop that runs from k to the length of the string s minus 1. This loop slides a window of length k along the string s, counting the number of vowels in each substring of length k.

6. Inside the loop, the method checks if the character i-k is a vowel. If it is, it decrements the count variable by 1.

7. The method then checks if the character i is a vowel. If it is, it increments the count variable by 1.

8. The method updates the max variable to be the maximum value of max and count.

9. Finally, the method returns the value of max.

The time complexity of the given code is O(n), where n is the length of the input string s. This is because we iterate through the input string twice, once to count the number of vowels in the first k characters, and then again to slide a window of length k over the string and count the number of vowels in each substring of length k. The time complexity of each iteration is O(1), so the overall time complexity is O(n).

The space complexity of the given code is O(1). This is because we only use a fixed amount of additional space to store two integer variables, max and count, regardless of the size of the input string. Therefore, the space used by the algorithm is constant and does not depend on the input size.

Conclusion:

The initial approach which I have taken has the optimal time and space complexity i.e., O(n) & O(1).

Thanks for reading..Happy learning....😊