k-Substring Vowels Editorial

Practice Problem Link: 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 number of vowels in every 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 store it in a list.

Analysis

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

Implementation

C++

vector<int> kSubstringVowels(string s, int k) {
	int n = s.length();
	vector<int> result(n - k + 1);
	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[iterator] = counter;
				iterator++;
			}
		}
	}
	return result;
}

Java

class Solution {
	int[] kSubstringVowels (String s, int k) {
		int n = s.length();
		int[] result = new int[n - k + 1];
		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[iterator] = counter;
					iterator++;
				}
			}
		}
		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, and store all the answers.

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;
}
vector<int> kSubstringVowels(string s, int k) {
	int n = s.length();
	vector<int> vowels(n + 1 - k);
	int count = 0;
	for (int i = 0; i < k; i++) {
		count += isVowel(s[i]);
	}
	vowels[0] = count;
	for (int i = k; i < n; i++) {
		count = count - isVowel(s[i - k]) + isVowel(s[i]);
		vowels[i - k + 1] = count;
	}
	return vowels;
}

Java

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

	int[] kSubstringVowels (String s, int k) {
		int n = s.length();
		int[] vowels = new int[n + 1 - k];
		int count = 0;
		for (int i = 0; i < k; i++) {
			count += isVowel(s.charAt(i));
		}
		vowels[0] = count;
		for (int i = k; i < n; i++) {
			count = count - isVowel(s.charAt(i - k)) + isVowel(s.charAt(i));
			vowels[i - k + 1] = count;
		}

		return vowels;
	}
}