LeetCode 3305 - Count of Substrings Containing Every Vowel and K Consonants I

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem asks us to count all substrings of a given string word that satisfy two conditions simultaneously: first, the substring must contain all five vowels 'a', 'e', 'i', 'o', and 'u' at least once; second, the substring must contain exactly k consonants. The input is a string of lowercase English letters, and a non-negative integer k. The output is an integer representing the number of substrings that meet these criteria.

The constraints clarify the problem’s scale: the string length is between 5 and 250 characters, ensuring that brute-force substring generation is feasible but could be inefficient if not optimized. Additionally, k is bounded between 0 and word.length - 5, which makes sense because a substring must have at least 5 characters to accommodate all vowels.

Important edge cases include strings where no substring contains all vowels, k equals 0, substrings with repeated vowels, and overlapping substrings that still satisfy the condition. The problem guarantees that the input contains only lowercase letters, simplifying character checks.

Approaches

The brute-force approach generates all possible substrings, checks if each substring contains all vowels, and counts the consonants to see if it equals k. This approach is guaranteed to be correct but inefficient, with a time complexity of approximately O(n^3) because there are O(n^2) substrings and counting vowels/consonants in each substring takes O(n).

The optimal approach leverages a sliding window technique. Since we are searching for substrings containing all vowels and exactly k consonants, we can maintain a dynamic window with two pointers. We track the counts of vowels in a hash map and the number of consonants separately. The window expands until all vowels are included and the consonant count reaches k. When both conditions are satisfied, we can increment a result counter and move the left pointer to explore new substrings efficiently. This reduces the unnecessary recomputation from the brute-force approach.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Generate all substrings and check each one for vowel and consonant criteria
Optimal	O(n^2)	O(1)	Sliding window with vowel count hash map and consonant counter

Algorithm Walkthrough

Initialize two pointers, left and right, to define the sliding window boundaries. Set vowel_count as a dictionary to track occurrences of 'a', 'e', 'i', 'o', 'u'. Initialize consonant_count to zero and result to zero.
Iterate right over the string word from 0 to len(word)-1. For each character, increment the corresponding vowel count if it is a vowel, otherwise increment consonant_count.
While the current window satisfies all five vowels and exactly k consonants, increment result by one. Then attempt to shrink the window from the left to look for other substrings: decrement the left character’s count in vowel_count if it is a vowel, or decrement consonant_count if it is a consonant. Increment left.
Continue expanding and shrinking the window until right reaches the end of the string.
Return result as the total number of valid substrings.

Why it works: The sliding window guarantees that every substring considered maintains the invariant of containing all vowels at least once and exactly k consonants. By expanding right and contracting left, all potential substrings are examined without recomputing counts from scratch, ensuring correctness and efficiency.

Python Solution

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        n = len(word)
        result = 0

        for start in range(n):
            vowel_count = {v: 0 for v in vowels}
            consonant_count = 0
            for end in range(start, n):
                char = word[end]
                if char in vowels:
                    vowel_count[char] += 1
                else:
                    consonant_count += 1
                if all(vowel_count[v] > 0 for v in vowels) and consonant_count == k:
                    result += 1
        return result

The Python implementation iterates over all possible starting points. For each starting index, it counts vowels and consonants dynamically as the end pointer extends the substring. It checks whether all vowels are present and consonants equal k, incrementing result if both conditions are satisfied. This direct implementation avoids recalculating counts from scratch for every substring.

Go Solution

func countOfSubstrings(word string, k int) int {
    vowels := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    n := len(word)
    result := 0

    for start := 0; start < n; start++ {
        vowelCount := map[rune]int{'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
        consonantCount := 0
        for end := start; end < n; end++ {
            char := rune(word[end])
            if vowels[char] {
                vowelCount[char]++
            } else {
                consonantCount++
            }
            if vowelCount['a'] > 0 && vowelCount['e'] > 0 && vowelCount['i'] > 0 &&
               vowelCount['o'] > 0 && vowelCount['u'] > 0 && consonantCount == k {
                result++
            }
        }
    }
    return result
}

In Go, the implementation mirrors Python. A map tracks vowel counts, a separate integer tracks consonants, and nested loops iterate over all possible substrings. The same checks are applied to increment the result counter.

Worked Examples

Example 1: word = "aeioqq", k = 1

Start at 0: "aeioq" → missing 'u' → not counted.

Start at 1: "eioqq" → missing 'a' → not counted.

No substrings satisfy conditions → output 0.

Example 2: word = "aeiou", k = 0

Start at 0: "aeiou" contains all vowels, consonant count 0 → counted → result 1.

No other substrings are valid → output 1.

Example 3: word = "ieaouqqieaouqq", k = 1

Tracking valid substrings manually: "ieaouq", "qieaou", "ieaouq" → output 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Nested loops over start and end indices. Counting vowels and consonants is O(1) per step.
Space	O(1)	Fixed-size hash map for vowels and a few integer counters.

Although we iterate over all substrings, we maintain constant space and avoid recomputation beyond what is necessary for counting vowels/consonants.

Test Cases

# Provided examples
assert Solution().countOfSubstrings("aeioqq", 1) == 0  # no substring has all vowels
assert Solution().countOfSubstrings("aeiou", 0) == 1  # only the whole word
assert Solution().countOfSubstrings("ieaouqqieaouqq", 1) == 3  # multiple valid substrings

# Edge cases
assert Solution().countOfSubstrings("aeiou", 5) == 0  # k exceeds available consonants
assert Solution().countOfSubstrings("aaaaaeeeiioouu", 0) == 1  # repeated vowels only
assert Solution().countOfSubstrings("aeiouxyz", 3) == 1  # exactly k consonants at the end
assert Solution().countOfSubstrings("aeiouxaeiouy", 1) == 2  # overlapping substrings
assert Solution().countOfSubstrings("aeiou", 1) == 0  # k=1 but no consonants

Test	Why
`"aeioqq", 1`	No valid substring with all vowels
`"aeiou", 0`	Minimal substring with all vowels, zero consonants
`"ieaouqqieaouqq", 1`	Multiple valid overlapping substrings
`"aeiou", 5`	k too large, cannot satisfy
`"aaaaaeeeiioouu", 0`	Only vowels repeated, tests repeated vowels
`"aeiouxyz", 3`	k consonants at the end of substring
`"aeiouxaeiouy", 1`	Overlapping substrings tested
`"aeiou", 1`	No consonants present, cannot satisfy k=1

Edge Cases

The first important edge case is when k exceeds the number of consonants in the string. For example, "aeiou", k = 5" will never have a valid substring because no substring has 5 consonants. The algorithm correctly handles this by never incrementing the result