3305. Count of Substrings Containing Every Vowel and K Consonants I

MediumHash TableStringSliding Window

Problem Description

You are given a string word and a non-negative integer k.

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 key to solving this problem is to transform it into two subproblems. First, calculate the number of substrings where each vowel appears at least once and there are at least k consonants (f(k)). Second, calculate the count of substrings where every vowel appears at least once with at least k + 1 consonants (f(k + 1)). The solution is then the difference between these two results, f(k) - f(k + 1).

To implement this, use a sliding window approach combined with a hash table to keep track of the vowels in the current window and a variable to count the consonants. As you traverse through the word, expand the window by adding characters to it. If a vowel is encountered, update the hash table; if a consonant is encountered, increase the consonant count.

When the number of consonants in the window meets or exceeds k and all vowels are present, calculate valid substrings that end with the current character. Move the left boundary of the window to reduce its size iteratively until the condition is no longer met. By doing so, you count how many valid starting points exist for substrings ending at the current position. Continue this process until you traverse the entire string.

Finally, compute the result by subtracting f(k + 1) from f(k), eliminating substrings with more than k consonants.

Learn more about Sliding Window patterns.

Solution Approach

The solution employs a sliding window approach with a hash table to effectively count substrings that satisfy the problem's criteria.

Steps:

Function Definition: Define a helper function f(String word, int k) that returns the count of substrings with each vowel appearing at least once and containing at least k consonants.
Initialize Variables:
- ans: A counter variable to store the result.
- l: The left boundary of the sliding window, initialized to 0.
- x: A counter for the number of consonants in the current window.
- cnt: A hash table to maintain the occurrences of each vowel in the current window.
Traverse the String:
- For each character c in word:
  - If c is a vowel, update the count in the hash table cnt.
  - If c is a consonant, increment the consonant counter x.
Adjust Window:
- While x is greater than or equal to k and the size of cnt (number of unique vowels) is 5:
  - Move the left boundary by removing the character at l from the window.
  - Update cnt for vowels and decrement x for consonants accordingly.
  - Increment l to shrink the window from the left.
Count Valid Substrings:
- If conditions are met, all substrings ending at the current index and starting positions less than l are valid.
- Add l to ans to account for these valid substrings.
Final Calculation:
- Compute f(k) and f(k + 1) using the helper function.
- Return the difference f(k) - f(k + 1) to get the count of substrings exactly containing k consonants.

This approach leverages a sliding window pattern to efficiently process the string in linear time, making use of a hash table to manage vowel occurrences within the window.

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 walk through a small example to comprehend the solution approach. Consider the string word = "aeiobccdeiou" and k = 2. We aim to count the substrings that include every vowel ('a', 'e', 'i', 'o', 'u') at least once and precisely 2 consonants.

Initialization: Start with ans = 0, l = 0, x = 0, and cnt = {} to track vowel occurrences.
Sliding Window Setup: Traverse the string from left to right.
- At index 0, character is 'a'. It's a vowel, so increment cnt['a']. Since it's not a consonant, x remains 0.
- At index 1, character is 'e'. Similarly, increment cnt['e'].
- At index 2, character is 'i'. Increment cnt['i'].
- At index 3, character is 'o'. Increment cnt['o'].
- At index 4, character is 'b'. It's a consonant, increment x to 1.
- At index 5, character is 'c'. It's another consonant, increment x to 2.
Check and Count: At this point, x = 2, but not all vowels are present (cnt doesn't have 'u' yet), so we continue traversing.
Complete Vowel Set:
- At index 6, character is 'c', still a consonant, increment x to 3.
- At index 7, character is 'd', a consonant, increase x to 4.
- At index 8, character is 'e'. It's a vowel, update cnt['e'].
- At index 9, character is 'i', update cnt['i'].
- At index 10, character is 'o', update cnt['o'].
- At index 11, character is 'u'. Finally, update cnt['u'] and now all vowels are present.
Adjust Window:
- From index 11, use the sliding window to adjust l while maintaining at least 2 consonants and all vowels:
  - Increment l to 5, remove 'b', x is now 3, but all vowels still covered in cnt.
Calculate Substrings:
- From l = 5 to current index 11, valid substrings exist: add l = 5 to ans, updating ans = 5.
Repeat for f(k + 1): Follow the same steps for calculating substrings with at least 3 consonants. Subtract this from the result above to obtain substrings with exactly 2 consonants.

The method measures optimality by iterating through the string with minimal overhead using the sliding window, making it efficient for larger inputs.

Solution Implementation

1def countOfSubstrings(word: str, k: int) -> int:
2    # Helper function to calculate the number of substrings based on conditions
3    def f(k: int) -> int:
4        ans = 0  # Resultant count of substrings
5        l = 0    # Left pointer for the sliding window
6        x = 0    # Counter for non-vowel characters
7        cnt = {}  # Dictionary to count occurrences of vowels
8
9        # Function to check if a character is a vowel
10        def is_vowel(char: str) -> bool:
11            return char in {'a', 'e', 'i', 'o', 'u'}
12
13        # Traverse each character in the word
14        for c in word:
15            # If the character is a vowel, increase its count in the dictionary
16            if is_vowel(c):
17                cnt[c] = cnt.get(c, 0) + 1
18            else:
19                # If not a vowel, increment the non-vowel counter
20                x += 1
21
22            # Adjust the window to maintain exactly 'k' non-vowel characters and all vowels present in the window
23            while x >= k and len(cnt) == 5:
24                d = word[l]
25                l += 1
26                if is_vowel(d):
27                    cnt[d] -= 1
28                    if cnt[d] == 0:
29                        del cnt[d]
30                else:
31                    x -= 1
32
33            # Add the count of the valid substring starting with each l up to the current position
34            ans += l
35
36        return ans
37
38    # Subtract the results of f(k) and f(k+1) to get the exact count for 'k' non-vowel substrings with all vowels
39    return f(k) - f(k + 1)
40

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int countOfSubstrings(String word, int k) {
6        // Calculate the difference between the numbers of substrings with at most 'k' non-vowels and 'k+1' non-vowels
7        return f(word, k) - f(word, k + 1);
8    }
9
10    private int f(String word, int k) {
11        int ans = 0; // Initialize the answer to 0
12        int l = 0; // This is the left index of the current substring window
13        int nonVowelCount = 0; // Counts non-vowels in the current window
14        Map<Character, Integer> countVowels = new HashMap<>(5); // Stores counts of vowels within the current window
15
16        // Iterate over each character in the word
17        for (char c : word.toCharArray()) {
18            if (isVowel(c)) {
19                // If current character is a vowel, update its count in the map
20                countVowels.merge(c, 1, Integer::sum);
21            } else {
22                // If it's a non-vowel, increment the non-vowel count
23                ++nonVowelCount;
24            }
25
26            // Adjust the window when the number of non-vowels is too high and we have all vowels in the map
27            while (nonVowelCount >= k && countVowels.size() == 5) {
28                char charAtLeft = word.charAt(l++); // Move the left index to the right
29
30                if (isVowel(charAtLeft)) {
31                    // If it's a vowel, decrease its count
32                    if (countVowels.merge(charAtLeft, -1, Integer::sum) == 0) {
33                        countVowels.remove(charAtLeft); // Remove the vowel if its count drops to zero
34                    }
35                } else {
36                    // If it's a non-vowel, decrease the non-vowel count
37                    --nonVowelCount;
38                }
39            }
40            ans += l; // Add the left index position to the answer
41        }
42        return ans; // Return the total calculated value
43    }
44
45    private boolean isVowel(char c) {
46        // Determine if the given character is a vowel
47        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
48    }
49}
50

1#include <unordered_map>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    // Main function to count the number of substrings with a specific condition
8    int countOfSubstrings(string word, int k) {
9        // Lambda function to compute result for a given k value
10        auto f = [&](int k) -> int {
11            int ans = 0;  // Variable to store the total count of substrings
12            int left = 0; // Left pointer for the sliding window
13            int nonVowelCount = 0; // Count the number of non-vowel characters in the current window
14            unordered_map<char, int> vowelCount; // Map to store frequencies of vowels found in the sliding window
15
16            // Helper lambda to check if a character is a vowel
17            auto isVowel = [&](char c) -> bool {
18                return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
19            };
20
21            // Iterate through each character in the word
22            for (char c : word) {
23                if (isVowel(c)) { // Check if the character is a vowel
24                    vowelCount[c]++; // Increment vowel count in the map
25                } else {
26                    ++nonVowelCount; // Increment the non-vowel count
27                }
28
29                // Adjust the window to ensure it does not contain more than 'k' non-vowel characters
30                while (nonVowelCount >= k && vowelCount.size() == 5) {
31                    char removedChar = word[left++]; // Slide the window, remove the character at the left
32                    if (isVowel(removedChar)) {
33                        if (--vowelCount[removedChar] == 0) {
34                            vowelCount.erase(removedChar); // Erase from map if count of the vowel is zero
35                        }
36                    } else {
37                        --nonVowelCount; // Decrease the count if a non-vowel is removed
38                    }
39                }
40
41                ans += left; // Add the count of valid starting points for substrings ending at the current position
42            }
43            return ans; // Return the computed number of valid substrings
44        };
45
46        // Return the difference between counts for k and k+1 to find exact matches of k length
47        return f(k) - f(k + 1);
48    }
49};
50

1function countOfSubstrings(word: string, k: number): number {
2    // Helper function to calculate the number of substrings based on conditions
3    const f = (k: number): number => {
4        let ans = 0; // Resultant count of substrings
5        let l = 0;   // Left pointer for the sliding window
6        let x = 0;   // Counter for non-vowel characters
7        const cnt = new Map<string, number>(); // Map to count occurrences of vowels
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        for (const c of word) {
15            // If the character is a vowel, increase its count in the map
16            if (isVowel(c)) {
17                cnt.set(c, (cnt.get(c) || 0) + 1);
18            } else {
19                // If not a vowel, increment the non-vowel counter
20                x++;
21            }
22
23            // Adjust the window to maintain exact 'k' non-vowel characters
24            // and all vowels present in the window
25            while (x >= k && cnt.size === 5) {
26                const d = word[l++];
27                if (isVowel(d)) {
28                    cnt.set(d, cnt.get(d)! - 1);
29                    if (cnt.get(d) === 0) {
30                        cnt.delete(d);
31                    }
32                } else {
33                    x--;
34                }
35            }
36            // Add the current valid substring count to the result
37            ans += l;
38        }
39
40        return ans;
41    };
42
43    // Subtract the results of f(k) and f(k+1) to get the exact count for 'k' non-vowel substrings with all vowels
44    return f(k) - f(k + 1);
45}
46

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 each character of the string is processed once, and operations on the Map run in constant time. Specifically, the main operations involve iterating over the characters and updating the character count, which are both linear in terms of complexity.

The space complexity is O(1). Although a Map is used, it never stores more than a constant number of keys (specifically up to 5 for vowels), meaning the space usage does not scale with the input size but remains constant.

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

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don’t know