3306. Count of Substrings Containing Every Vowel and K Consonants II

MediumHash TableStringSliding Window

Problem Description

You are given a string word and a non-negative integer k. You need to 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.

Intuition

The solution is built upon the idea of transforming the problem into solving two related subproblems that allow us to calculate the desired number of substrings efficiently. Here's the step-by-step thought process:

Subproblem Decomposition:
- First, understand that counting the exact number of consonants along with the presence of all vowels is complex. We simplify this by finding substrings with at least k consonants first, denoted by a function f(k).
- Then, find the number of substrings with at least k + 1 consonants, denoted by f(k + 1).
Calculate the Desired Count:
- The number of substrings with exactly k consonants is obtained by subtracting the two results: f(k) - f(k + 1).
Sliding Window Technique:
- Use a sliding window to traverse the string while maintaining a count of vowels and consonants.
- Utilize a hash table cnt to keep track of the occurrences of each vowel within the current window.
- A variable x is used to count the number of consonants in the current window.
- The left boundary l of the sliding window is adjusted dynamically based on the condition that x >= k and all vowels are present.
Efficient Counting:
- As we slide the window from left to right, for each position, the substrings ending at the current position with the appropriate criteria are counted. This is determined by checking the constraints (x >= k and vowel count) and incrementing the substring count by the length of the valid window.

This approach results in efficient computation of the count of substrings meeting the specified conditions. The difference f(k) - f(k + 1) yields the desired number of substrings containing all vowels and exactly k consonants.

Learn more about Sliding Window patterns.

Solution Approach

The solution leverages a combination of problem transformation and the sliding window technique to efficiently count the required substrings. Here's the detailed walkthrough of the implementation:

Problem Transformation:
- We define a helper function f(k) to calculate the number of substrings containing at least k consonants and all vowels at least once.
- Compute two values: f(k) and f(k + 1), as the difference will yield the count of substrings with exactly k consonants.
Sliding Window Technique:
- Use a sliding window approach to efficiently traverse the string, adjusting the window size dynamically to maintain the required conditions.
- Initialize a counter cnt to track occurrences of each vowel, an integer x to count consonants, and an integer l to represent the left boundary of the window.
- As we iterate over each character in the string:
  - If it's a vowel, update the cnt with this vowel.
  - If it's a consonant, increment x.
  - When x (the number of consonants) is at least k and the number of different vowels in cnt is 5 (indicating all vowels are present), adjust the window by moving l to the right, decrementing counts appropriately.
Counting Valid Substrings:
- For each valid window, all substrings that start from the valid range [0...l-1] and end at the current position are counted. This is added to the result for f(k).
Final Calculation:
- Return the difference between f(k) and f(k+1) to find the number of substrings with exactly k consonants and all vowels present.

The algorithm effectively uses a hash map to maintain counts and a simple sliding window to ensure efficient processing of the string, reducing potential complexity by focusing on valid vowel and consonant distributions dynamically.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a simple example:

Suppose we have the string word = "beautiful" and k = 2.

Transform the Problem:
- We need to find substrings that contain all vowels (a, e, i, o, u) at least once and exactly 2 consonants.
Sliding Window Technique:
- Initialize a hash table cnt to track occurrences of each vowel, set integer x = 0 to count consonants, and integer l = 0 as the left boundary of the sliding window.
Traverse the String:
- Index 0 ('b'):
  - It's a consonant, increment x to 1.
  - We don't have all vowels yet, so no valid substrings.
- Index 1 ('e'):
  - It's a vowel, update cnt['e'] to 1.
  - Still don't have all vowels or enough consonants, so no valid substrings.
- Index 2 ('a'):
  - Vowel found, update cnt['a'] to 1.
  - Condition still not met for valid substrings.
- Index 3 ('u'):
  - Vowel found, update cnt['u'] to 1.
  - Condition still not met for valid substrings.
- Index 4 ('t'):
  - Consonant found, increment x to 2.
  - We have 2 consonants, but still missing vowels i and o, so no valid substrings.
- Index 5 ('i'):
  - Vowel found, update cnt['i'] to 1.
  - Condition still not met due to missing o.
- Index 6 ('f'):
  - Consonant found, increment x to 3.
  - Adjust the left boundary l while keeping all vowels and x >= 2.
  - Valid substring found as beauti.
- Index 7 ('u'):
  - Vowel found but already counted in cnt.
  - Valid substrings: beautif, eautif, autif, utif, tif, if (all within current window boundaries).
- Index 8 ('l'):
  - Consonant found, increment x to 4.
  - Adjust the left boundary l to maintain valid conditions while x >= 2.
  - Valid substrings: beautiful, eautiful, autiful, utiful, tiful, iful (all within current window boundaries).
Calculate f(k) and f(k + 1):
- f(k): Count substrings with at least 2 consonants where all vowels appear.
- f(k + 1): Count substrings with at least 3 consonants where all vowels appear.
- Result: The difference f(2) - f(3) gives the final count of required substrings.

Using the sliding window efficiently allows us to count and adjust dynamically without generating each substring explicitly, ensuring performance stays optimal. This demonstrates how transforming the problem and applying efficient techniques can resolve complexities effectively.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def countOfSubstrings(self, word: str, k: int) -> int:
5        # Helper function to calculate the count based on vowel conditions
6        def f(k: int) -> int:
7            cnt = Counter()  # Counter to track occurrences of vowels
8            ans = l = x = 0  # Initialize answer, left pointer, and non-vowel count
9          
10            for c in word:  # Iterate through each character in the word
11                if c in "aeiou":  # Check if the character is a vowel
12                    cnt[c] += 1  # Increment the counter for this vowel
13                else:
14                    x += 1  # Increment non-vowel count if character is not a vowel
15              
16                # Adjust the left pointer
17                while x >= k and len(cnt) == 5:  # Check if all vowels present and x is at least k
18                    d = word[l]  # Get the character at the left pointer
19                    if d in "aeiou":  # If it is a vowel
20                        cnt[d] -= 1  # Decrement the counter for this vowel
21                        if cnt[d] == 0:  # If no more of this vowel, remove it from the counter
22                            cnt.pop(d)
23                    else:
24                        x -= 1  # Decrement non-vowel count
25                    l += 1  # Move the left pointer to the right
26              
27                ans += l  # Add current left pointer position to answer
28          
29            return ans  # Return the result
30      
31        # The result is the difference between counts with k and k+1 non-vowel conditions
32        return f(k) - f(k + 1)
33

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    // Method to calculate the count of valid substrings of length k
6    public long countOfSubstrings(String word, int k) {
7        // Calculate the difference between the results of f for k and k+1
8        // This helps to find the exact count of valid substrings of length k
9        return f(word, k) - f(word, k + 1);
10    }
11
12    // Helper method to calculate the potential substrings
13    private long f(String word, int k) {
14        long answer = 0; // Accumulator for the count of valid substrings
15        int left = 0; // Left pointer for the sliding window
16        int nonVowelCount = 0; // Counter for non-vowel characters in the window
17
18        // Map to store counts of vowels within the current window
19        Map<Character, Integer> countMap = new HashMap<>(5);
20
21        // Iterate through each character in the word
22        for (char c : word.toCharArray()) {
23            // If the character is a vowel, update its count in the map
24            if (vowel(c)) {
25                countMap.merge(c, 1, Integer::sum);
26            } else {
27                // If not a vowel, increase the non-vowel counter
28                ++nonVowelCount;
29            }
30
31            // While the non-vowel count is at least k and all vowels are present
32            while (nonVowelCount >= k && countMap.size() == 5) {
33                // Get the character at the left pointer
34                char d = word.charAt(left++);
35              
36                // If it is a vowel, decrease its count in the map
37                if (vowel(d)) {
38                    if (countMap.merge(d, -1, Integer::sum) == 0) {
39                        countMap.remove(d); // Remove from map if count becomes zero
40                    }
41                } else {
42                    // Decrease the non-vowel counter if the character was non-vowel
43                    --nonVowelCount;
44                }
45            }
46
47            // Accumulate the number of valid starting points for the substrings
48            answer += left;
49        }
50
51        return answer;
52    }
53
54    // Utility method to determine if a character is a vowel
55    private boolean vowel(char c) {
56        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
57    }
58}
59

1#include <string>
2#include <unordered_map>
3
4class Solution {
5public:
6    long long countOfSubstrings(std::string word, int k) {
7        // Lambda function to calculate substrings with at least k non-vowel chars
8        auto substringCount = [&](int k) -> long long {
9            long long answer = 0;
10            int left = 0, nonVowels = 0;
11            std::unordered_map<char, int> vowelCount;
12
13            // Helper lambda function to check if a character is a vowel
14            auto isVowel = [&](char c) -> bool {
15                return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
16            };
17
18            // Iterate through each character in the word
19            for (char c : word) {
20                // If it's a vowel, increase its count in the map
21                if (isVowel(c)) {
22                    vowelCount[c]++;
23                } else {
24                    // If it's not a vowel, increment the non-vowel counter
25                    ++nonVowels;
26                }
27
28                // Adjust the window from the left until the constraints are met
29                while (nonVowels >= k && vowelCount.size() == 5) {
30                    char leftChar = word[left++];
31                    if (isVowel(leftChar)) {
32                        if (--vowelCount[leftChar] == 0) {
33                            vowelCount.erase(leftChar);
34                        }
35                    } else {
36                        --nonVowels;
37                    }
38                }
39
40                // Add the number of valid starting positions to the answer
41                answer += left;
42            }
43
44            return answer;
45        };
46
47        // Calculate the result for exactly k non-vowels by subtracting results
48        return substringCount(k) - substringCount(k + 1);
49    }
50};
51

1function countOfSubstrings(word: string, k: number): number {
2    // Helper function that calculates the number of valid substrings
3    const f = (maxConsonants: number): number => {
4        let totalSubstrings = 0; // Initialize the count of valid substrings
5        let leftIndex = 0; // Start index for the sliding window
6        let consonantCount = 0; // Count of consonants in the current window
7        const vowelCount = new Map<string, number>(); // Map to count occurrences of each vowel in the current window
8
9        // Function to check if a character is a vowel
10        const isVowel = (char: string): boolean => {
11            return char === 'a' || char === 'e' || char === 'i' || char === 'o' || char === 'u';
12        };
13
14        // Iterate through each character in the word
15        for (const char of word) {
16            if (isVowel(char)) {
17                // If the current character is a vowel, update its count in the map
18                vowelCount.set(char, (vowelCount.get(char) || 0) + 1);
19            } else {
20                // If it is a consonant, increase the consonant count
21                consonantCount++;
22            }
23
24            // Adjust the window size if conditions are not met
25            while (consonantCount >= maxConsonants && vowelCount.size === 5) {
26                const leftChar = word[leftIndex++]; // Get the character at the left end of the window and increment the index
27                if (isVowel(leftChar)) {
28                    vowelCount.set(leftChar, vowelCount.get(leftChar)! - 1);
29                    if (vowelCount.get(leftChar) === 0) {
30                        // Remove the vowel from the map if its count reaches zero
31                        vowelCount.delete(leftChar);
32                    }
33                } else {
34                    // Decrease the consonant count if the character at the left end is a consonant
35                    consonantCount--;
36                }
37            }
38            // Add the count of valid substrings ending at the current character
39            totalSubstrings += leftIndex;
40        }
41
42        return totalSubstrings;
43    };
44
45    // Calculate the difference between valid substrings with k and k + 1 consonants
46    return f(k) - f(k + 1);
47}
48

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string word. This is because the function f iterates through the string word once, and each character is processed in constant time.

The space complexity of the code is O(1). The space used by the Counter cnt is limited since it only stores up to 5 vowel characters, leading to constant space usage. Other variables such as ans, l, x, and the parameter k also use constant space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know