Count of Substrings Containing Every Vowel and K Consonants II

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,

• for a sliding window solution, we obviously need minimum 2 pointers, l and r1.
  • intuitively, it makes sense that we should increment r1 until we have a valid substring
    • this is because you can add more vowels to this sliding window to form more valid substrings

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

complexity

• Time: O(n)
• Space: O(1)

learnings

• for loops are a lot more versatile than you think; they do not just have to run until i < array.size()