You are given a string word and a non-negative integer k.
Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.
Example 1:
Input: word = "aeioqq", k = 1
Output: 0
Explanation:
There is no substring with every vowel.
Example 2:
Input: word = "aeiou", k = 0
Output: 1
Explanation:
The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".
Example 3:
Input: word = "ieaouqqieaouqq", k = 1
Output: 3
Explanation:
The substrings with every vowel and one consonant are:
word[0..5], which is "ieaouq".word[6..11], which is "qieaou".word[7..12], which is "ieaouq".
Constraints:
5 <= word.length <= 2 * 105word consists only of lowercase English letters.0 <= k <= word.length - 5class Solution {
public long countOfSubstrings(String word, int k) {
return atLeastK(word, k) - atLeastK(word, k + 1);
}
private long atLeastK(String word, int k) {
long numValidSubstrings = 0;
int start = 0;
int end = 0;
// keep track of counts of vowels and consonants
HashMap<Character, Integer> vowelCount = new HashMap<>();
int consonantCount = 0;
// start sliding window
while (end < word.length()) {
// insert new letter
char newLetter = word.charAt(end);
// update counts
if (isVowel(newLetter)) {
vowelCount.put(
newLetter,
vowelCount.getOrDefault(newLetter, 0) + 1
);
} else {
consonantCount++;
}
// shrink window while we have a valid substring
while (vowelCount.size() == 5 && consonantCount >= k) {
numValidSubstrings += word.length() - end;
char startLetter = word.charAt(start);
if (isVowel(startLetter)) {
vowelCount.put(
startLetter,
vowelCount.get(startLetter) - 1
);
if (vowelCount.get(startLetter) == 0) {
vowelCount.remove(startLetter);
}
} else {
consonantCount--;
}
start++;
}
end++;
}
return numValidSubstrings;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}