3306: Count-of-Substrings-Containing-Every-Vowel-and-K-Consonants-II
Medium

My love for the sliding window is wavering. This is mainly due the number of edge cases this question has.

It makes perfect sense to use a sliding window for this problem, as we are trying to count the number of contiguous non-empty substrings. However, there are a lot of conditions we need to satisfy, such as having to track the number of unique vowels and the number of consonants. We do this with an integer array, letter_count[6], where letter_count[0] counts the consonants and letter_count[1] to letter_count[5] counts the vowels

Now, all there is to do is to address the main logic behind the algorithm,

but how should we track all these subsequent valid substrings?

this is where our 3rd pointer comes in r2
- we initialise r2 = r1, and continue to iterate r2 until it reaches a consonant (or the end of word)
  - this implies that all the indices between r1 and r2 are vowels
- then, as long as we know there exist 5 unique vowels and number of consonants, letter_count[0], is equal to k, r2 - r1 + 1 is equal to the total number of valid substrings beginning from index position l

the next problem is that, since this is a sliding window solution, we have to increment l somehow:

it makes intuitive sense that we should be incrementing l after we find all the possible valid substrings starting from index l
if we increment, we have to make sure we remove word[l]:
- if word[l] is a consonant, then we can just stop iterating through l
  - we know that there are less than k consonants now, so we can start from the beginning and increment r1 instead
- if word[l] is a vowel:
  - if there are no more word[l] letters remaining in word:
    - implies that there are only 4 unique vowels now
    - we can increment r1 until we get either 5 unique vowels now or we reach r2
    - then we just add r2-r1+1 to ans if we have 5 unique vowels
  - if there are more word[l] letters remaining in word:
    - we can simply just add r2-r1+1 to ans

The main problem now, is that implementing this logic might be slightly difficult.

Code:

class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        int l = 0;
        int r1 = 0;
        int r2 = 0;

        int vowel_count = 0;
        unordered_map<char, int> mp {{'a', 1}, {'e', 2}, {'i', 3}, {'o', 4}, {'u', 5}};
        int letter_count[6] = {0};

        long long ans = 0;

        while (r2 < word.size()) {
            for (; r1 < word.size() && ((vowel_count < 5 && mp[word[r1]]) || letter_count[0] < k); ++r1) {
                int index = mp[word[r1]];
                if (letter_count[index]++ == 0 && index) {
                    ++vowel_count;
                }
            }

            for (r2 = r1; r2 < word.size() && mp[word[r2]] > 0; ++r2);

            for (; l < r2 && letter_count[0] == k; ++l) {
                for (; r1 < r2 && (vowel_count < 5); ++r1) {
                    int index = mp[word[r1]];
                    if (letter_count[index]++ == 0 && index) {
                        ++vowel_count;
                    }
                }

                if (vowel_count == 5) ans += (r2-r1)+1;

                if (int index = mp[word[l]]; --letter_count[index] == 0 && index) {
                    --vowel_count;
                }
            }

            if (!k && l == r2 && r2 < word.size()) {
                ++l;
                ++r1;
                ++r2;
            }
        }
        return ans;
    }
};

3306: Count-of-Substrings-Containing-Every-Vowel-and-K-Consonants-II
Medium

Code:

Complexity:

Learnings:

3306: Count-of-Substrings-Containing-Every-Vowel-and-K-Consonants-II Medium

Code:

Complexity:

Learnings:

3306: Count-of-Substrings-Containing-Every-Vowel-and-K-Consonants-II
Medium