1456, Maximum Number of Vowels in a Substring of Given Length

1456, Maximum Number of Vowels in a Substring of Given Length

Hi, folks today I am here with an interesting coding problem from Leetcode.
To directly go to the question please click here.
So I will walk through the solution. It will be a brute force and an optimized way solution. I will be explaining the optimized way solutions in depth.

# Intuition
For any substring of length k, we need to find how many vowels are there in it and provide the highest count of all counts of vowels in a substring.

Test Case 1

Input k = 2 and s='asjdee'
Output - 2
Explanation: As for substring of length k=2, in the string 's' we have 'ee' when the length is k and the vowels count is 2

Test Case 2

Input k=3 and s='aasdiisdwe'
Output - 2
Explanation - For all the substrings with length k = 3 we have 'aas' and 'dii' with 2 vowels each in it.

Brute Force - Looping (twice) - Gives TLE (Not recommended)

# Approach
Create a hashmap (dictionary) with all the vowels in it.
Loop through the string till len(s)-k element of string as we will be looping through (i, i+k) substring inside of it.

# Complexity
- Time complexity: O(Nk)
- Space complexity: O(N) - creating a hashmap

# Code
```
class Solution:
   def maxVowels(self, s: str, k: int) -> int:

       l = {'a':0, 'e':0, 'i':0, 'o':0, 'u':0}
       mx=0
       for i in range(0, len(s)-k+1):
           count = 0
           print(i, i+k)
           for j in range(i, i+k):
               if s[j] in l:
                   count+=1
           mx = max(mx, count)

       return mx
```

Optimised way - Sliding Window

# Intuition

For any substring of length k, we need to find how many vowels are there in it.

# Approach

Create a hashmap with all the vowels as keys and any value as value. (it will help in searching of vowels space complexity O(n) and search complexity of O(1). Pretty good.:p).
Set two pointers to start and end and initialize them as 0. It is for extracting the substring of length k. For other variables as count and mx, set them as 0 as well.
`count` is to get the count of vowels in the current string and `mx` is to store the max count of vowels in any given string.
We will be using the while loop and setting conditions for `end` to reach the last element of the `s`.
Now till the substring is of length `k` we will keep incrementing `end` and meanwhile make sure to check if the current element is in hashmap or not and increase the count accordingly.
Once the condition for substring length is met, we will store the max count of vowels in the given length of the substring. After that, we start to increment `start` by 1 and we need to check if an element in the start is also a vowel before incrementing it. if it is a vowel then reduce the count by 1.

# Complexity
- Time complexity: O(N)

- Space complexity: O(N) - Because we create a hashmap (dictionary) of all the vowels.

# Code
```
class Solution:
   def maxVowels(self, s: str, k: int) -> int:
       start = 0
       end = 0
       mx = 0
       count = 0
       l = {'a':0, 'e':0, 'i':0, 'o':0, 'u':0}
       while end<len(s):
           if s[end] in l:
               count+=1
           if end-start+1==k:
               mx=max(mx, count)
               if s[start] in l:
                   count-=1
               start+=1
           end+=1
       return mx
```
Leetcode Profile - Prajwal Ahluwalia
Do follow me for more.

Comments