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 * 105wordconsists only of lowercase English letters.0 <= k <= word.length - 5
Approach 01:
-
C++
-
Python
#include <unordered_map>
#include <string>
#include <algorithm>
class Solution {
public:
long long countOfSubstrings(std::string word, int maxNonVowel) {
return countSubstringsWithAtMost(word, maxNonVowel) -
countSubstringsWithAtMost(word, maxNonVowel - 1);
}
private:
long countSubstringsWithAtMost(const std::string& word, int maxNonVowel) {
if (maxNonVowel == -1)
return 0;
long substringCount = 0;
int vowelCount = 0;
int uniqueVowelCount = 0;
std::unordered_map<char, int> lastVowelPosition;
for (int left = 0, right = 0; right < word.length(); ++right) {
if (isVowel(word[right])) {
++vowelCount;
if (const auto it = lastVowelPosition.find(word[right]);
it == lastVowelPosition.end() || it->second < left)
++uniqueVowelCount;
lastVowelPosition[word[right]] = right;
}
while (right - left + 1 - vowelCount > maxNonVowel) {
if (isVowel(word[left])) {
--vowelCount;
if (lastVowelPosition[word[left]] == left)
--uniqueVowelCount;
}
++left;
}
if (uniqueVowelCount == 5) {
substringCount += std::min({
lastVowelPosition['a'], lastVowelPosition['e'],
lastVowelPosition['i'], lastVowelPosition['o'],
lastVowelPosition['u']
}) - left + 1;
}
}
return substringCount;
}
bool isVowel(char character) {
static constexpr std::string_view vowels = "aeiou";
return vowels.find(character) != std::string_view::npos;
}
};
Time Complexity:
- Sliding Window Traversal:
Both calls to
countSubstringsWithAtMostuse a two-pointer approach (left and right), ensuring each character is processed at most twice, resulting in \( O(n) \) complexity. - Map Operations:
Updating and accessing
lastVowelPositiontakes \( O(1) \) per operation, leading to \( O(n) \) total operations. - Total Time Complexity:
Since
countSubstringsWithAtMostis called twice, the overall complexity remains \( O(n) \).
Space Complexity:
- Map Storage:
The unordered map
lastVowelPositionstores at most 5 vowel positions, contributing to \( O(1) \) space. - Other Variables:
All other variables use \( O(1) \) additional space.
- Total Space Complexity:
The overall space complexity is \( O(1) \).
from collections import defaultdict
class Solution:
def countOfSubstrings(self, word: str, maxNonVowel: int) -> int:
return (self._countSubstringsWithAtMost(word, maxNonVowel) -
self._countSubstringsWithAtMost(word, maxNonVowel - 1))
def _countSubstringsWithAtMost(self, word: str, maxNonVowel: int) -> int:
if maxNonVowel == -1:
return 0
substringCount = 0
vowelCount = 0
uniqueVowelCount = 0
lastVowelPosition = {}
left = 0
for right in range(len(word)):
if self._isVowel(word[right]):
vowelCount += 1
if word[right] not in lastVowelPosition or lastVowelPosition[word[right]] < left:
uniqueVowelCount += 1
lastVowelPosition[word[right]] = right
while right - left + 1 - vowelCount > maxNonVowel:
if self._isVowel(word[left]):
vowelCount -= 1
if lastVowelPosition[word[left]] == left:
uniqueVowelCount -= 1
left += 1
if uniqueVowelCount == 5:
substringCount += min(
lastVowelPosition.get('a', float('inf')),
lastVowelPosition.get('e', float('inf')),
lastVowelPosition.get('i', float('inf')),
lastVowelPosition.get('o', float('inf')),
lastVowelPosition.get('u', float('inf'))
) - left + 1
return substringCount
def _isVowel(self, character: str) -> bool:
return character in "aeiou"
Time Complexity:
- Sliding Window Traversal:
Both
_countSubstringsWithAtMostcalls iterate through the string using two pointers (left and right), ensuring each character is processed at most twice. This results in \( O(n) \) complexity. - Dictionary Operations:
Each vowel update in
lastVowelPositionis \( O(1) \), and fetching the minimum last position of all vowels is \( O(1) \), leading to \( O(n) \) overall operations. - Total Time Complexity:
The function calls
_countSubstringsWithAtMosttwice, making the final complexity \( O(n) \).
Space Complexity:
- Dictionary Storage:
The dictionary
lastVowelPositionstores at most 5 vowel positions, contributing to \( O(1) \) space. - Other Variables:
All other variables use \( O(1) \) additional space.
- Total Space Complexity:
The overall space complexity is \( O(1) \).