Maximum k-Substring Vowels Editorial

Practice Problem Link: Maximum k-Substring Vowels

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s and a number k, find the maximum number of vowels in any substring of size k.

Vowels: ['a', 'e', 'i', 'o', 'u']

Naive Approach

The naive approach is to iterate over all the subarrays in the array, and if it is of length k, we can calculate the number of vowels in it and calculate the maximum out of them.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(1)

Implementation

C++

int maxKSubstringVowels(string s, int k) {
	int n = s.length();
	int result = 0;
	int iterator = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			if(j - i + 1 == k) {
				int counter = 0;
				for(int l = i; l <= j; l++) {
					if(s[l] == 'a' || s[l] == 'e' || s[l] == 'i' || s[l] == 'o' || s[l] == 'u') {
						counter++;
					}
				}
				result = max(result, counter);
			}
		}
	}
	return result;
}

Java

class Solution {
	int maxKSubstringVowels (String s, int k) {
		int n = s.length();
		int result = 0;
		int iterator = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(j - i + 1 == k) {
					int counter = 0;
					for(int l = i; l <= j; l++) {
						if(s.charAt(l) == 'a' || s.charAt(l) == 'e' || s.charAt(l) == 'i' || s.charAt(l) == 'o' || s.charAt(l) == 'u') {
							counter++;
						}
					}
					result = Math.max(result, counter);
				}
			}
		}
		return result;
	}
}

Optimal Approach

We will use the sliding window technique to calculate the number of vowels in subarrays of size k in linear time. Using the sliding window technique we can check if the elements deleted and added into the window is a vowel or not based on which we change our answer. Then we will take the maximum answer over all the subarrays.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int isVowel(char c) {
	if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
		return 1;
	}
	return 0;
}
int maxKSubstringVowels(string s, int k) {
	int n = s.length();
	int count = 0;
	for (int i = 0; i < k; i++) {
		count += isVowel(s[i]);
	}

	int maxCount = count;
	for (int i = k; i < n; i++) {
		count = count - isVowel(s[i - k]) + isVowel(s[i]);
		maxCount = max(maxCount, count);
	}

	return maxCount;
}

Java

class Solution {
	int isVowel(char c) {
		if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
			return 1;
		}
		return 0;
	}

	int maxKSubstringVowels (String s, int k) {
		int n = s.length();
		int count = 0;
		for (int i = 0; i < k; i++) {
			count += isVowel(s.charAt(i));
		}

		int maxCount = count;
		for (int i = k; i < n; i++) {
			count = count - isVowel(s.charAt(i - k)) + isVowel(s.charAt(i));
			maxCount = Math.max(maxCount, count);
		}

		return maxCount;
	}
}