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

table of contents

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?

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

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;
    }
};

complexity

learnings