Count of Substrings Containing Every Vowel and K Consonants 1

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:

1
2
3
4
5
6
7
8



Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

1
2
3
4
5
6
7
8
9



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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12



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 <= 250
word consists only of lowercase English letters.
0 <= k <= word.length - 5

Solution

Method 1 - Sliding Window

This problem is very similar to Count of Substrings Containing Every Vowel and K Consonants 2, but with relaxed constraints. So, instead of returning long we return int.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68



class Solution {
    public int 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
        int 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


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.

Problem#

Examples#

Solution#

Method 1 - Sliding Window#

Code#

Complexity#