Count of Substrings Containing Every Vowel and K Consonants 2

Problem

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.

Examples

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 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.
• 0 <= k <= word.length - 5

Solution

Method 1 - Sliding Window

Here is the approach:

1. Use the Sliding Window Technique: We maintain a window ([leftPointer, rightPointer]) over the string and expand or shrink it based on the problem's constraints:

   • Expand the window by moving rightPointer and updating counts for vowels or consonants.
   • Shrink the window by moving leftPointer if excess consonants are present (> k).

2. Track Key Metrics:

   • distinctVowelCount: Number of unique vowels in the current window.
   • vowelCount[0]: Tracks consonant count. Other indices in vowelCount track counts of vowels (a, e, i, o, u).

3. Check Valid Substrings:

   • A substring is valid when:
     • All 5 vowels are present (distinctVowelCount == 5).
     • Exactly k consonants (vowelCount[0] == k).

4. Count Valid Substrings Using midPointer: When the window is valid:

   • Use midPointer to efficiently count substrings starting from leftPointer and ending at each valid position.

Finally:

1. Initialise leftPointer, midPointer, distinctVowelCount, vowelCount, and result.
2. Iterate through the string with rightPointer, processing each character:
   • Update vowel and consonant counts.
   • Shrink the window if consonant count exceeds k.
   • Count valid substrings when the window satisfies the constraints.
3. Return result.

Code

Java

class Solution {
    public long countOfSubstrings(String word, int k) {
        String vowels = "aeiou";
        int leftPointer = 0, midPointer = 0, distinctVowelCount = 0;
        int[] vowelCount = new int[6]; // Tracks counts of vowels (and consonants at index 0)
        int[] countedVowels = new int[6]; // Tracks seen vowels for substring calculations
        long result = 0;

        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            int vowelIndex = vowels.indexOf(currentChar) + 1;

            // Update consonant count or vowel count
            if (vowelIndex == 0) {
                vowelCount[0]++; // Increment consonant count
            } else {
                vowelCount[vowelIndex]++;
                if (vowelCount[vowelIndex] == 1) {
                    distinctVowelCount++;
                }
            }

            // Shrink the window from the left if consonants exceed `k`
            while (vowelCount[0] > k) {
                char leftChar = word.charAt(leftPointer);
                int leftVowelIndex = vowels.indexOf(leftChar) + 1;

                if (leftVowelIndex == 0) {
                    vowelCount[0]--; // Reduce consonant count
                } else {
                    vowelCount[leftVowelIndex]--;
                    if (vowelCount[leftVowelIndex] == 0) {
                        distinctVowelCount--;
                    }
                }
                leftPointer++;
            }

            // Check if the current window is valid
            if (distinctVowelCount == 5 && vowelCount[0] == k) {
                // Adjust midPointer and counted vowels
                if (midPointer < leftPointer) {
                    midPointer = leftPointer;
                    Arrays.fill(countedVowels, 0);
                }

                while (midPointer <= i) {
                    char midChar = word.charAt(midPointer);
                    int midVowelIndex = vowels.indexOf(midChar) + 1;

                    if (midVowelIndex == 0 || 
                        vowelCount[midVowelIndex] - countedVowels[midVowelIndex] == 1) {
                        break;
                    }

                    countedVowels[midVowelIndex]++;
                    midPointer++;
                }

                // Count substrings
                result += midPointer - leftPointer + 1;
            }
        }

        return result;
    }
}

Python

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        vowels = "aeiou"
        left_pointer, mid_pointer = 0, 0
        distinct_vowel_count = 0
        vowel_count = [0] * 6  # Tracks counts of vowels and consonants (index 0 for consonants)
        counted_vowels = [0] * 6  # Tracks seen vowels for substring calculations
        result = 0

        for i, char in enumerate(word):
            vowel_index = vowels.find(char) + 1

            # Update consonant count or vowel count
            if vowel_index == 0:
                vowel_count[0] += 1  # Increment consonant count
            else:
                vowel_count[vowel_index] += 1
                if vowel_count[vowel_index] == 1:
                    distinct_vowel_count += 1

            # Shrink the window from the left if consonants exceed `k`
            while vowel_count[0] > k:
                left_char = word[left_pointer]
                left_vowel_index = vowels.find(left_char) + 1

                if left_vowel_index == 0:
                    vowel_count[0] -= 1  # Reduce consonant count
                else:
                    vowel_count[left_vowel_index] -= 1
                    if vowel_count[left_vowel_index] == 0:
                        distinct_vowel_count -= 1

                left_pointer += 1

            # Check if the current window is valid
            if distinct_vowel_count == 5 and vowel_count[0] == k:
                # Adjust mid_pointer and counted vowels
                if mid_pointer < left_pointer:
                    mid_pointer = left_pointer
                    counted_vowels = [0] * 6
                
                while mid_pointer <= i:
                    mid_char = word[mid_pointer]
                    mid_vowel_index = vowels.find(mid_char) + 1

                    if mid_vowel_index == 0 or \
                    vowel_count[mid_vowel_index] - counted_vowels[mid_vowel_index] == 1:
                        break

                    counted_vowels[mid_vowel_index] += 1
                    mid_pointer += 1

                # Count substrings
                result += mid_pointer - left_pointer + 1

        return result

Complexity

• ⏰ Time complexity: O(n), as we iterate through the string - O(n)
• 🧺 Space complexity: O(1), since we use a constant amount of extra space.