# Maximum Number of Vowels in a Substring of Given Length In this article, we will look at an interesting problem related to the Strings and [Sliding-Window Algorithm](https://java2blog.com/sliding-window-maximum-java/ “Sliding-Window Algorithm”). The problem is : `"Given a String we have to Find the Maximum Number of Vowel Letters present in any Substring of the String, with the length of each Substring equal to K."`

Let us understand this statement with some Sample inputs:

Now, we will discuss different approaches to solve the problem and analyze their complexities.

## Approach – 1 Generate All Substrings Using substring() Method

• Basically, we will iterate throughout the length of the String and generate [all substrings](https://java2blog.com/find-all-substrings-of-string-in-java/ “all substrings”) of the given length K using the `substring()` method present in `String` class of `java.lang` package.
• We Keep a Variable maxVowels which will be used to track the Maximum Vowels for a substring. So, For each substring, we count the number of Vowels in it and update the maxVowels.
• To count the number of vowels in a substring, we implement `countVowelsInSubstring()`, a method which given a substring will return the count of Vowels in it.

Let us look at the code for this approach:

`Output:`

`Time Complexity:` Generating a Substring of size K using `substring()` method takes O(K) time and we do this for N-K characters taking total `O( (N-K) * K )` time. Now, for each substring of size K, we count the vowels in it which takes total `O( K * K) = O(K2)` time, so the Overall [time complexity](https://java2blog.com/introduction-to-complexity-of-algorithm/ “time complexity”) will be : `O( N*K -K2 + K2) = O(N * K)`. This is a naïve solution for this problem.

## Approach – 2 Using Sliding Window Method (Linear Time Solution)

The intention behind this approach is to give a Linear Runtime Solution(O(n)) to this problem. For this, we are going to use the idea of the Sliding Window Method. We follow these steps:

• At first, we will calculate the number of vowels in the first window of size K i.e. from the index 0 to K-1 as `countVowels`. We have a variable `maxVowels` that keeps track of the maximum number of vowels in a window.
• If the First Window has vowels we update the maxVowels. Then we start traversing from index K throughout the length of the String and calculate the vowels in each window. Consider the String `"java2blog"` the vowels present at different windows of the string is shown below:
• We use the idea of prefix array, after getting the vowels in 1st window, we start from the index `K`, if the character at index K is a vowel we increment the `countVowels` and if the character at the index `i - k` is a Vowel we decrement `countVowels` by 1. This step ensures the window slides to the right in every iteration.
• Finally, we update the `maxVowels` for each window that we process.

Now, let us have a look at the implementation of above approach in Code:

`Output:`

`Time Complexity:` Basically, We slide the window throughout the length of string, N, and traverse each character only once. For each character, we check whether it is a Vowel which is an O(1) operation. So the Time Complexity of this approach is `O(N)` and gives an optimal solution to the problem.

That’s all about maximum number of vowels in a substring of Given Length, you can try the code with different examples considering all edge cases.

## Related Posts

• 04 June

### Search for a range Leetcode – Find first and last position of element in sorted array

Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […]

• 30 April

### Convert Postfix to Infix in Java

Learn about how to convert Postfix to Infix in java.

• 30 April

### Convert Prefix to Postfix in Java

Learn about how to convert Prefix to Postfix in java.

• 16 April

### Data Structures in java

• 29 November

### Top 100+ Java coding interview questions

Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]

• 18 April

### Minimum Number of Jumps to reach last Index

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find Minimum Number of Jumps to reach last Index. Problem Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a […]

## Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.