3569. Count of Substrings Containing Every Vowel and K Consonants II
My accepted Python solution to LeetCode problem 3569, Count of Substrings Containing Every Vowel and K Consonants II, running in 1479ms.
- Difficulty: Medium
- Python
- Runtime 1479ms
- Memory 19.1MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 1479ms, memory 19.1MB, accepted 2026-01-01.
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
# Use sliding window: count substrings with >= k consonants and all vowels
# minus count of substrings with >= k+1 consonants and all vowels
def atLeastK(word, k):
# Count substrings with at least k consonants and all 5 vowels
vowels = set('aeiou')
n = len(word)
result = 0
vowel_count = {}
consonants = 0
left = 0
for right in range(n):
c = word[right]
if c in vowels:
vowel_count[c] = vowel_count.get(c, 0) + 1
else:
consonants += 1
# Shrink window while we have all vowels and enough consonants
while len(vowel_count) == 5 and consonants >= k:
# All substrings ending at right starting from [left, right - sufficient] are valid
result += n - right
left_char = word[left]
if left_char in vowels:
vowel_count[left_char] -= 1
if vowel_count[left_char] == 0:
del vowel_count[left_char]
else:
consonants -= 1
left += 1
return result
return atLeastK(word, k) - atLeastK(word, k + 1)