Problem Statement
Brute Force [TLE]
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
vowels = {'a', 'e', 'i', 'o', 'u'}
left = 0
N = len(word)
res = 0
def isValid(l, r, word, k_val):
curr_vowels = set()
for i in range(l, r + 1):
c = word[i]
if c in vowels:
curr_vowels.add(c)
else:
k_val -= 1
return k_val == 0 and curr_vowels == vowels
for right in range(N):
if right >= (5 + k - 1):
r = right
while r < N:
if isValid(left, r, word, k):
res += 1
r += 1
left += 1
return res
Editorial
Approach 1: Sliding Window
class Solution:
def _isVowel(self, c: str) -> bool:
return c == "a" or c == "e" or c == "i" or c == "o" or c == "u"
def countOfSubstrings(self, word: str, k: int) -> int:
num_valid_substrings = 0
start = end = 0
vowel_count = {} # Dictionary to keep counts of vowels
consonant_count = 0 # Count of consonants
next_consonant = [0] * len(
word
) # Array to compute index of next consonant for all indices
next_consonant_index = len(word)
for i in range(len(word) - 1, -1, -1):
next_consonant[i] = next_consonant_index
if not self._isVowel(word[i]):
next_consonant_index = i
while end < len(word):
new_letter = word[end]
if self._isVowel(new_letter):
vowel_count[new_letter] = vowel_count.get(new_letter, 0) + 1
else:
consonant_count += 1
while (
consonant_count > k
): # Shrink window if too many consonants are present
start_letter = word[start]
if self._isVowel(start_letter):
vowel_count[start_letter] -= 1
if vowel_count[start_letter] == 0:
del vowel_count[start_letter]
else:
consonant_count -= 1
start += 1
while (
start < len(word)
and len(vowel_count) == 5
and consonant_count == k
): # Try to shrink if window is valid
num_valid_substrings += next_consonant[end] - end
start_letter = word[start]
if self._isVowel(start_letter):
vowel_count[start_letter] -= 1
if vowel_count[start_letter] == 0:
del vowel_count[start_letter]
else:
consonant_count -= 1
start += 1
end += 1
return num_valid_substrings
Approach 2: Sliding Window (Relaxed Constraints)
class Solution:
def _isVowel(self, c: str) -> bool:
return c in ["a", "e", "i", "o", "u"]
def _atLeastK(self, word: str, k: int) -> int:
num_valid_substrings = 0
start = 0
end = 0
# keep track of counts of vowels and consonants
vowel_count = {}
consonant_count = 0
# start sliding window
while end < len(word):
# insert new letter
new_letter = word[end]
# update counts
if self._isVowel(new_letter):
vowel_count[new_letter] = vowel_count.get(new_letter, 0) + 1
else:
consonant_count += 1
# shrink window while we have a valid substring
while len(vowel_count) == 5 and consonant_count >= k:
num_valid_substrings += len(word) - end
start_letter = word[start]
if self._isVowel(start_letter):
vowel_count[start_letter] = (
vowel_count.get(start_letter) - 1
)
if vowel_count.get(start_letter) == 0:
vowel_count.pop(start_letter)
else:
consonant_count -= 1
start += 1
end += 1
return num_valid_substrings
def countOfSubstrings(self, word: str, k: int) -> int:
return self._atLeastK(word, k) - self._atLeastK(word, k + 1)
