3306. Count of Substrings Containing Every Vowel and K Consonants II

Problem Statement

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.

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 * 105

• word consists only of lowercase English letters.

• 0 <= k <= word.length - 5

Intuition

Links

https://leetcode.com/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii/description/

Video Links

Approach 1:

Basically, from Loop 1, Get desired size of 5, 
Meaning all vowels and k cons

Then Maintain nextCons array tracking the next cons
That means when,

All strings between nextCons are coveres

ex
     l    x
aeiouqaaaaq
All Strings from x-l are covered by next loop 

C++

class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        long long ans = 0;
        int n = word.size();
        unordered_set<char> s = {'a', 'e', 'i', 'o', 'u'};
        unordered_map<char, int> mp;
        
        vector<int> nextCons(n);
        nextCons[n-1] = n;
        for(int i=n-2; i>=0; i--){
            if(s.count(word[i+1])){
                nextCons[i] = nextCons[i+1];
            }
            else{
                nextCons[i] = i+1;
            }
        }
        
        int con = 0;
        int low, high;


        for(low=0, high=0; high<word.size(); high++){
            if(s.count(word[high])){
                mp[word[high]]++;
                // Vow
            }
            else{
                con ++;
            }

            while(con > k){
                char lowChar = word[low];
                if(s.count(lowChar)){
                    if(mp[lowChar] == 1)
                        mp.erase(lowChar);
                    else
                        mp[lowChar]--;
                }
                else{
                    con --;
                }

                low++;
            }

            while(mp.size() == 5 and con == k){
                ans += nextCons[high] - high;
                char lowChar = word[low];
                if(s.count(lowChar)){
                    if(mp[lowChar] == 1)
                        mp.erase(lowChar);
                    else
                        mp[lowChar]--;
                }
                else{
                    con --;
                }

                low++;
            }
        }

        return ans;
    }

};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems