LeetCode 3306 - Count of Substrings Containing Every Vowel and K Consonants II

LeetCode Problem 3306

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

Solution

Problem Understanding

The problem asks us to count how many substrings of a given string satisfy two conditions simultaneously:

1. The substring contains all five vowels, 'a', 'e', 'i', 'o', and 'u', at least once.
2. The substring contains exactly k consonants.

The input consists of:

• A lowercase English string word
• A non-negative integer k

A substring is a contiguous portion of the string. We must examine every possible substring and count only those that satisfy both requirements.

The important detail is that vowels may appear multiple times. The condition is only that every vowel appears at least once. At the same time, the substring must contain exactly k consonants, not at most or at least.

For example, if word = "aeiou" and k = 0, the entire string is valid because it contains all five vowels and no consonants.

The constraints are very important:

• word.length can be as large as 2 * 10^5
• A brute force solution that checks all substrings would be far too slow
• We need an algorithm close to linear time

The input is guaranteed to contain only lowercase English letters, so vowel checking is straightforward.

Several edge cases are important:

• Strings that never contain all five vowels
• k = 0, where substrings must contain only vowels
• Strings with many repeated vowels
• Strings where consonants appear frequently
• Very large inputs, where efficiency becomes critical

Because the input size is large, we need an optimized sliding window solution.

Approaches

Brute Force Approach

The most direct approach is to generate every possible substring and check whether it satisfies the conditions.

For every starting index i, we expand the substring character by character toward the right. While expanding, we maintain:

• A count of consonants
• Frequency counts for vowels

Whenever the substring contains all five vowels and exactly k consonants, we increment the answer.

This approach is correct because it explicitly examines every substring. However, there are O(n^2) substrings, and checking each one may require additional work.

With n = 2 * 10^5, an O(n^2) solution is completely infeasible.

Optimal Approach

The key insight is that "exactly k consonants" can be transformed into:

substrings with at least k consonants
-
substrings with at least (k + 1) consonants

This is a common sliding window technique.

So instead of directly counting substrings with exactly k consonants, we define a helper function:

countAtLeast(k)

This function counts substrings that:

• contain all five vowels
• contain at least k consonants

Then:

exactly(k) = atLeast(k) - atLeast(k + 1)

Now the problem becomes easier because sliding windows naturally handle "at least" constraints.

We maintain:

• A left pointer
• A right pointer
• A vowel frequency map
• A consonant counter

As we expand the right pointer, we try to shrink the left pointer while the window remains valid.

Whenever the current window is valid, every larger window ending at the same right index is also valid. This allows us to count many substrings at once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every substring individually
Optimal	O(n)	O(1)	Sliding window with inclusion-exclusion

Algorithm Walkthrough

Step 1: Define a Helper Function

We create a helper function:

countAtLeast(minConsonants)

This function counts substrings that:

• contain all five vowels
• contain at least minConsonants consonants

Later we compute:

countAtLeast(k) - countAtLeast(k + 1)

to obtain substrings with exactly k consonants.

Step 2: Initialize Sliding Window State

We maintain:

• left, the left boundary of the window
• consonants, the number of consonants inside the window
• vowel_count, a hash map storing vowel frequencies
• result, the running total

The right pointer moves from left to right across the string.

Step 3: Expand the Window

For each character at index right:

• If it is a vowel, increment its frequency
• Otherwise increment consonants

At this point, the window is:

word[left:right+1]

Step 4: Shrink While Valid

A window is valid when:

• all five vowels exist in the frequency map
• consonants >= minConsonants

While the window remains valid:

• remove word[left]
• move left forward

This shrinking process finds the smallest invalid prefix boundary.

Step 5: Count Valid Substrings

After shrinking stops, every starting position before left forms a valid substring ending at right.

Therefore:

result += left

This is the key optimization.

Instead of counting substrings individually, we count all valid starting positions at once.

Step 6: Compute the Final Answer

Finally:

answer = countAtLeast(k) - countAtLeast(k + 1)

This removes all substrings with more than k consonants, leaving only those with exactly k.

Why it works

The sliding window maintains the invariant that all windows starting before left are valid, while the current window starting at left is invalid.

For each right, the number of valid substrings ending at right is exactly left.

Using inclusion-exclusion:

exactly(k) = atLeast(k) - atLeast(k + 1)

ensures that substrings with more than k consonants are removed, leaving only substrings with exactly k consonants.

Python Solution

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        vowels = set("aeiou")

        def count_at_least(min_consonants: int) -> int:
            left = 0
            consonants = 0
            vowel_count = {}
            total = 0

            for right, ch in enumerate(word):
                if ch in vowels:
                    vowel_count[ch] = vowel_count.get(ch, 0) + 1
                else:
                    consonants += 1

                while len(vowel_count) == 5 and consonants >= min_consonants:
                    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

                total += left

            return total

        return count_at_least(k) - count_at_least(k + 1)

The implementation follows the exact sliding window strategy described earlier.

The helper function count_at_least maintains a dynamic window using two pointers. As the right pointer expands, the window accumulates characters. The frequency map tracks which vowels are currently present.

The while loop attempts to shrink the window as much as possible while preserving validity. Once shrinking stops, every earlier starting position is guaranteed to form a valid substring ending at the current right index.

The final answer uses inclusion-exclusion:

atLeast(k) - atLeast(k + 1)

which isolates substrings containing exactly k consonants.

Go Solution

func countOfSubstrings(word string, k int) int64 {
	vowels := map[byte]bool{
		'a': true,
		'e': true,
		'i': true,
		'o': true,
		'u': true,
	}

	countAtLeast := func(minConsonants int) int64 {
		left := 0
		consonants := 0
		total := int64(0)

		vowelCount := make(map[byte]int)

		for right := 0; right < len(word); right++ {
			ch := word[right]

			if vowels[ch] {
				vowelCount[ch]++
			} else {
				consonants++
			}

			for len(vowelCount) == 5 && consonants >= minConsonants {
				leftChar := word[left]

				if vowels[leftChar] {
					vowelCount[leftChar]--

					if vowelCount[leftChar] == 0 {
						delete(vowelCount, leftChar)
					}
				} else {
					consonants--
				}

				left++
			}

			total += int64(left)
		}

		return total
	}

	return countAtLeast(k) - countAtLeast(k+1)
}

The Go implementation closely mirrors the Python version.

The primary difference is explicit type handling. The result uses int64 because the number of substrings can exceed the range of a standard 32-bit integer.

Go also requires explicit map deletion when a vowel count becomes zero.

Worked Examples

Example 1

word = "aeioqq"
k = 1

No substring contains all five vowels because 'u' never appears.

Result:

0

Example 2

word = "aeiou"
k = 0

We compute:

atLeast(0) - atLeast(1)

Counting atLeast(0)

right	char	window	vowels present	consonants	left after shrink	added
0	a	"a"	1	0	0	0
1	e	"ae"	2	0	0	0
2	i	"aei"	3	0	0	0
3	o	"aeio"	4	0	0	0
4	u	"aeiou"	5	0	1	1

Total = 1

Counting atLeast(1)

No window has at least one consonant.

Total = 0

Final answer:

1 - 0 = 1

Example 3

word = "ieaouqqieaouqq"
k = 1

Valid substrings are:

"ieaouq"
"qieaou"
"ieaouq"

Result:

3

As the sliding window moves, the algorithm dynamically tracks vowel coverage and consonant counts, efficiently counting all valid windows without enumerating every substring.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves at most n times
Space	O(1)	Only fixed-size vowel tracking structures are used

The sliding window guarantees linear complexity because both pointers move monotonically from left to right.

The vowel frequency map stores at most five entries, so the auxiliary space remains constant.

Test Cases

sol = Solution()

# Provided examples
assert sol.countOfSubstrings("aeioqq", 1) == 0  # missing vowel u
assert sol.countOfSubstrings("aeiou", 0) == 1  # single valid substring
assert sol.countOfSubstrings("ieaouqqieaouqq", 1) == 3  # multiple matches

# Minimal valid case
assert sol.countOfSubstrings("aeiou", 1) == 0  # no consonants available

# All vowels with repeats
assert sol.countOfSubstrings("aaeeiioouu", 0) == 4  # multiple vowel-only substrings

# Single consonant around vowels
assert sol.countOfSubstrings("qaeiou", 1) == 1  # consonant at front
assert sol.countOfSubstrings("aeiouq", 1) == 1  # consonant at end

# Multiple consonants
assert sol.countOfSubstrings("qaeiouq", 2) == 1  # whole string only

# No valid substring
assert sol.countOfSubstrings("bbbbbbbb", 1) == 0  # no vowels

# Large consonant blocks
assert sol.countOfSubstrings("bbbbbaeioubbbbb", 5) >= 1  # stress consonant counting

# Repeated valid regions
assert sol.countOfSubstrings("aeiouaeiou", 0) > 1  # overlapping windows

Test Case Summary

Test	Why
"aeioqq", 1	Missing one vowel
"aeiou", 0	Smallest valid input
"ieaouqqieaouqq", 1	Multiple valid windows
"aeiou", 1	Impossible consonant requirement
"aaeeiioouu", 0	Repeated vowels
"qaeiou", 1	Consonant at beginning
"aeiouq", 1	Consonant at end
"qaeiouq", 2	Exact consonant counting
"bbbbbbbb", 1	No vowels present
"bbbbbaeioubbbbb", 5	Large consonant sections
"aeiouaeiou", 0	Overlapping valid substrings

Edge Cases

Edge Case 1: No Complete Vowel Set

A string may never contain all five vowels. For example:

"aeioqq"

is missing 'u'.

A naive implementation might incorrectly count substrings that contain only some vowels. The sliding window avoids this because validity requires:

len(vowel_count) == 5

Without all five vowels present, no substring is counted.

Edge Case 2: k = 0

When k = 0, only vowel-only substrings are valid.

This case is tricky because many sliding window implementations accidentally treat zero as a special failure condition. Here, the inclusion-exclusion formula still works correctly:

exactly(0) = atLeast(0) - atLeast(1)

The algorithm naturally counts windows with zero consonants.

Edge Case 3: Repeated Vowels

Consider:

"aaeeiioouu"

The substring may contain many repeated vowels.

A buggy implementation might only track whether a vowel exists and incorrectly remove it when shrinking the window. This solution uses frequency counts instead of booleans.

A vowel is removed from the map only when its frequency becomes zero, ensuring correctness for repeated characters.