Problem Informations

• Problem Index: 3306
• Problem Link: Count of Substrings Containing Every Vowel and K Consonants II
• Topics: Hash Table, String, Sliding 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.

Example 1:

Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

Input: word = "aeiou", k = 0

Output: 1

Explanation:

The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".

Example 3:

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

• word[0..5], which is "ieaouq".
• word[6..11], which is "qieaou".
• word[7..12], which is "ieaouq".

Constraints:

• $5 \leq \text{word.length} \leq 2 \times 10^5$
• word consists only of lowercase English letters.
• $0 \leq k \leq \text{word.length} - 5$

Intuition

The problem requires identifying substrings that contain all five vowels (‘a’, ’e’, ‘i’, ‘o’, ‘u’) at least once and have exactly k consonants. The complexity lies in efficiently finding such substrings given the constraints, particularly the length of the word. The use of sliding window technique becomes essential here, as it allows dynamic adjustment of the window size and position to evaluate different candidate substrings without needing to re-evaluate the entire string repeatedly.

Approach

The solution employs a sliding window approach to maintain a dynamic substring within the given word. The process involves several steps, executed iteratively for each character in the string:

1. Mapping Characters: A helper function is used to map each character to an index, with vowels mapped to indices 0-4 and consonants mapped to index 5.

2. Dynamic Window Adjustment: As the right end of the window expands with each iteration, it updates a count array that tracks the number of each vowel and the total number of consonants in the current window.

3. Consonant Count Restriction: If the window contains more consonants than the specified k, the left part of the window is incremented until the extra consonants are removed, ensuring the count is exactly k.

4. Preventing Vowel Duplication: To avoid counting substrings with duplicated vowels before all are present, the window deletes extra vowels by moving the right boundary forward until all included vowels are unique.

5. Validation and Accumulation: At each step, it checks whether the current window (substring) contains all vowels at least once and exactly k consonants by using min_element to ensure each vowel’s count is greater than zero and verifying the consonant count matches k. If a valid substring is found, it accumulates the number of such substrings.

The algorithm efficiently evaluates substrings using targeted adjustments to the window boundaries, ensuring that condition checks and window updates are performed in a manner that maximizes computational efficiency relative to the problem’s constraints.

Code

C++

class Solution {
public:
    // Function to map vowels and consonants to specific indices.
    // Vowels are mapped to 0-4, while any consonant is mapped to 5.
    int mapCharacterToIndex(char c) {
        switch(c) {
            case 'a': return 0;
            case 'e': return 1;
            case 'i': return 2;
            case 'o': return 3;
            case 'u': return 4;
            default:  return 5;
        }
    }
    
    long long countOfSubstrings(string word, int k) {
        // Count array to keep track of the number of vowels and consonants.
        vector<int> count(6, 0); 
        int left = 0, right = 0;
        long long answer = 0;

        for (int i = 0; i < word.size(); i++) {
            int index = mapCharacterToIndex(word[i]);
            count[index]++;

            // Adjust window if there are more than 'k' consonants.
            if (index == 5 && count[index] > k) {
                while (count[index] > k) {
                    count[mapCharacterToIndex(word[right++])]--;
                }
                left = right;
            }
            
            // Ensure no duplication of vowels.
            while (mapCharacterToIndex(word[right]) != 5 && count[mapCharacterToIndex(word[right])] > 1) {
                count[mapCharacterToIndex(word[right++])]--;
            }

            // Check if current substring contains all vowels and exactly k consonants.
            if (*min_element(count.begin(), count.end() - 1) > 0 && count[5] == k) {
                answer += right - left + 1;
            }
        }
        return answer;
    }
};

Python

class Solution:
    # Function to map vowels and consonants to specific indices.
    # Vowels are mapped to 0-4, while any consonant is mapped to 5.
    def mapCharacterToIndex(self, c):
        if c == 'a':
            return 0
        elif c == 'e':
            return 1
        elif c == 'i':
            return 2
        elif c == 'o':
            return 3
        elif c == 'u':
            return 4
        else:
            return 5
    
    def countOfSubstrings(self, word, k):
        # Count array to keep track of the number of vowels and consonants.
        count = [0] * 6
        left = 0
        right = 0
        answer = 0

        for i in range(len(word)):
            index = self.mapCharacterToIndex(word[i])
            count[index] += 1

            # Adjust window if there are more than 'k' consonants.
            if index == 5 and count[index] > k:
                while count[index] > k:
                    count[self.mapCharacterToIndex(word[right])] -= 1
                    right += 1
                left = right
            
            # Ensure no duplication of vowels.
            while self.mapCharacterToIndex(word[right]) != 5 and count[self.mapCharacterToIndex(word[right])] > 1:
                count[self.mapCharacterToIndex(word[right])] -= 1
                right += 1

            # Check if current substring contains all vowels and exactly k consonants.
            if min(count[:5]) > 0 and count[5] == k:
                answer += right - left + 1

        return answer

Complexity

• Time complexity: $O(n)$

  The algorithm iterates through the input string word once using a single loop, making the time complexity $O(n)$ where $n$ is the length of the string. Inside the loop, the algorithm performs constant-time operations, including updates on the count array and checks for conditions. The inner while loops move the right pointer to adjust the window, but collectively, they do not exceed $O(n)$ operations over the course of the algorithm because each character is processed at most twice (once when moving right forward and once, potentially, when moving right backward to maintain the window condition).

• Space complexity: $O(1)$

  The space complexity of the algorithm is $O(1)$, which indicates constant space usage. This is because the algorithm uses a fixed-size array of six integers to keep track of the count of vowels and consonants, and it does not use any data structures that scale with the size of the input string word. The only variables and data structures used have a size that is independent of the input size, thus resulting in a constant space complexity.