Skip to main content

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.


  1. 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(N*k)

- 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

```


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

Post a Comment

Popular posts from this blog

1235. Maximum Profit in Job Scheduling

Hi everyone, Today's post is little bit intriguing to me as it took me some time to get t the solution. I have been out of practice for a bit so I was not able to do it in the DP. I didn't want to copy the code. Though i understood the code after i checked its solution in the discussions. Anyways, i tried to do it with heap and with some thinking I was able to do it and with my surprise It performed real well. I would like to jump to the solution but first I would like to explain a little bit about heaps so you can get better understanding of the code. A heap is like a special type of list where the smallest (or largest) item is always at the front. Think of it like a priority line at a theme park, where the person with the highest priority goes to the front. There are two types of heaps: Min Heap: The smallest item is at the front. It's like standing in a line where the shortest person is always at the front. Max Heap: The largest item is at the front. It's like stand...
2 comments
Read more

Group Anagrams – Python Solution Explained

Problem Overview The Group Anagrams problem is a common challenge in coding interviews and competitive programming. The goal is to group a list of strings such that all anagrams are placed in the same group. Anagrams are words that contain the same characters but in different orders. For example, given the input ["eat", "tea", "tan", "ate", "nat", "bat"] , the expected output is [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] . Approach and Solution In this blog post, we'll discuss an efficient solution using Python's built-in data structures. The provided code uses a dictionary to group the anagrams. Here’s a step-by-step explanation of the approach: Code Breakdown Explanation Initialization: We use defaultdict from the collections module to create a dictionary ( hm ) where each key will map to a list of anagrams. This is useful because it automatically initializes ...
Post a Comment
Read more

What is a Processor?

Smartphones have been the most important part of our lives. We have seen the evolution of our  handsets. First we saw landlines which were mess of tangled wires then we saw mobile phones which is successor of landlines. They were portable devices from which you can make calls then we witnessed emergence of Smartphones which were  considered as portable computers which also allows us to make calls. What is a Processor? Underneath that touchscreen display there is a full- fledged computer that commands your apps so that they function properly. A processor executes what you want your smartphone to do or in other word you can say processor is brain of computer. there is Exynos, Snapdragon, quad-core octa-core etc. What is a core? It is an element of surprises. They are present inside processor and are responsible for reading the command and executing them. First devices came with single core processor but later on scientists invented more advanced processors such as dual core , So...
Post a Comment
Read more