3305. Count of Substrings Containing Every Vowel and K Consonants I LeetCode Solution
In this guide, you will get 3305. Count of Substrings Containing Every Vowel and K Consonants I LeetCode Solution with the best time and space complexity. The solution to Count of Substrings Containing Every Vowel and K Consonants I 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.
Table of Contents
- Problem Statement
- Complexity Analysis
- Count of Substrings Containing Every Vowel and K Consonants I solution in C++
- Count of Substrings Containing Every Vowel and K Consonants I solution in Java
- Count of Substrings Containing Every Vowel and K Consonants I solution in Python
- Additional Resources
Problem Statement of Count of Substrings Containing Every Vowel and K Consonants I
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 <= 250
word consists only of lowercase English letters.
0 <= k <= word.length – 5
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
3305. Count of Substrings Containing Every Vowel and K Consonants I LeetCode Solution in C++
class Solution {
public:
int 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.
int substringsWithAtMost(const string& word, int k) {
if (k == -1)
return 0;
int 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 */3305. Count of Substrings Containing Every Vowel and K Consonants I LeetCode Solution in Java
class Solution {
public int 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 int substringsWithAtMost(String word, int k) {
if (k == -1)
return 0;
int 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 PROGIEZ3305. Count of Substrings Containing Every Vowel and K Consonants I LeetCode Solution in Python
class Solution:
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 == -1:
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 PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.