In this guide, you will get 3306. Count of Substrings Containing Every Vowel and K Consonants II LeetCode Solution with the best time and space complexity. The solution to Count of Substrings Containing Every Vowel and K Consonants II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count of Substrings Containing Every Vowel and K Consonants II
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 * 105
word consists only of lowercase English letters.
0 <= k <= word.length – 5
3306. Count of Substrings Containing Every Vowel and K Consonants II LeetCode Solution in C++
class Solution {
public:
// Same as 3305. Count of Substrings Containing Every Vowel and K Consonants I
long long countOfSubstrings(string word, int k) {
return substringsWithAtMost(word, k) - substringsWithAtMost(word, k - 1);
}
private:
// Return the number of substrings containing every vowel with at most k
// consonants.
long substringsWithAtMost(const string& word, int k) {
if (k == -1)
return 0;
long res = 0;
int vowels = 0;
int uniqueVowels = 0;
unordered_map<char, int> vowelLastSeen;
for (int l = 0, r = 0; r < word.length(); ++r) {
if (isVowel(word[r])) {
++vowels;
if (const auto it = vowelLastSeen.find(word[r]);
it == vowelLastSeen.end() || it->second < l)
++uniqueVowels;
vowelLastSeen[word[r]] = r;
}
while (r - l + 1 - vowels > k) {
if (isVowel(word[l])) {
--vowels;
if (vowelLastSeen[word[l]] == l)
--uniqueVowels;
}
++l;
}
if (uniqueVowels == 5)
// Add substrings containing every vowel with at most k consonants to
// the answer. They are
// word[l..r], word[l + 1..r], ..., word[min(vowelLastSeen[vowel])..r]
res += min({vowelLastSeen['a'], vowelLastSeen['e'], vowelLastSeen['i'],
vowelLastSeen['o'], vowelLastSeen['u']}) -
l + 1;
}
return res;
}
bool isVowel(char c) {
static constexpr string_view kVowels = "aeiou";
return kVowels.find(c) != string_view::npos;
}
}; /* code provided by PROGIEZ */
3306. Count of Substrings Containing Every Vowel and K Consonants II LeetCode Solution in Java
class Solution {
// Same as 3305. Count of Substrings Containing Every Vowel and K Consonants I
public long countOfSubstrings(String word, int k) {
return substringsWithAtMost(word, k) - substringsWithAtMost(word, k - 1);
}
// Return the number of substrings containing every vowel with at most k
// consonants.
private long substringsWithAtMost(String word, int k) {
if (k == -1)
return 0;
long res = 0;
int vowels = 0;
int uniqueVowels = 0;
Map<Character, Integer> vowelLastSeen = new HashMap<>();
for (int l = 0, r = 0; r < word.length(); ++r) {
if (isVowel(word.charAt(r))) {
++vowels;
if (!vowelLastSeen.containsKey(word.charAt(r)) || vowelLastSeen.get(word.charAt(r)) < l)
++uniqueVowels;
vowelLastSeen.put(word.charAt(r), r);
}
while (r - l + 1 - vowels > k) {
if (isVowel(word.charAt(l))) {
--vowels;
if (vowelLastSeen.get(word.charAt(l)) == l)
--uniqueVowels;
}
++l;
}
if (uniqueVowels == 5) {
// Add substrings containing every vowel with at most k consonants to
// the answer. They are
// word[l..r], word[l + 1..r], ..., word[min(vowelLastSeen[vowel])..r]
final int minVowelLastSeen = Arrays.asList('a', 'e', 'i', 'o', 'u')
.stream()
.mapToInt(vowel -> vowelLastSeen.get(vowel))
.min()
.getAsInt();
res += minVowelLastSeen - l + 1;
}
}
return res;
}
private boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
} // code provided by PROGIEZ
3306. Count of Substrings Containing Every Vowel and K Consonants II LeetCode Solution in Python
class Solution:
# Same as 3305. Count of Substrings Containing Every Vowel and K Consonants I
def countOfSubstrings(self, word: str, k: int) -> int:
kVowels = 'aeiou'
def substringsWithAtMost(k: int) -> int:
"""
Return the number of substrings containing every vowel with at most k
consonants.
"""
if k < 0:
return 0
res = 0
vowels = 0
uniqueVowels = 0
vowelLastSeen = {}
l = 0
for r, c in enumerate(word):
if c in kVowels:
vowels += 1
if c not in vowelLastSeen or vowelLastSeen[c] < l:
uniqueVowels += 1
vowelLastSeen[c] = r
while r - l + 1 - vowels > k:
if word[l] in kVowels:
vowels -= 1
if vowelLastSeen[word[l]] == l:
uniqueVowels -= 1
l += 1
if uniqueVowels == 5:
# Add substrings containing every vowel with at most k consonants to
# the answer. They are
# word[l..r], word[l + 1..r], ..., word[min(vowelLastSeen[vowel])..r]
res += min(vowelLastSeen[vowel] for vowel in kVowels) - l + 1
return res
return substringsWithAtMost(k) - substringsWithAtMost(k - 1) # code by PROGIEZ
