Maximum Number of Vowels in a Substring of Given Length

Leetcode Daily Challenge (5th May, 2023)

5 May, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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

Link: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

Problem Explanation with examples:-

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 <= 105
s consists of lowercase English letters.
1 <= k <= s.length

Intuition:-

We will use a sliding window of size k to find the maximum number of vowels in a substring of size k.
At each step, we will add the vowel count of the current character and subtract the vowel count of the first character of the previous window.
We will keep track of the maximum vowel count and return it in the end.

Solution:-

Initialize a variable to store the vowel count of the current window.
Iterate over the first k characters of the string and add the vowel count of each character to the variable.
Initialize a variable to store the maximum vowel count and store the vowel count of the current window in it.
Iterate over the remaining characters of the string. Subtract the vowel count of the first character of the previous window from the variable. Add the vowel count of the current character to the variable.
Update the maximum vowel count if the vowel count of the current window is greater than it.
Return the maximum vowel count.

Code:-

JAVA Solution

class Solution {
    public int maxVowels(String s, int k) {
        String v = "aeiou";
        int c = 0;
        int n = s.length();
        for (int i = 0; i < k; i++) {
            if (v.indexOf(s.charAt(i)) != -1) {
                c++;
            }
        }
        int mx = c;
        for (int i = k; i < n; i++) {
            if (v.indexOf(s.charAt(i-k)) != -1) {
                c--;
            }
            if (v.indexOf(s.charAt(i)) != -1) {
                c++;
            }
            mx = Math.max(mx, c);
        }
        return mx;
    }
}

Python Solution

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        v = 'aeiou'
        c = 0
        n = len(s)
        for i in range(k):
            if s[i] in v:
                c += 1
        mx = c
        for i in range(k,n):
            if s[i-k] in v:
                c -= 1
            if s[i] in v:
                c += 1
            mx = max(mx,c)

        return mx

Complexity Analysis:-

TIME:-

The time complexity is O(n) where n is the length of the string. We iterate over the string once and perform constant time operations at each step.

SPACE:-

The space complexity is O(1) as we use constant extra space.

References:-

Sliding Window

Connect with me:-

java

python

leetcode

dsa