N^2 with Pruning

N^2 solutions sometimes can be pruned to a point that they actually work well. This is an example: we can solve in N^2 by going thru all the substrings, but if we get to a point where the count of consonants is less than zero, we skip the inner loop, cutting down the search time considerably. Code is down below, cheers, ACC.

Count of Substrings Containing Every Vowel and K Consonants I - LeetCode

3305. Count of Substrings Containing Every Vowel and K Consonants I

Medium

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

public class Solution {
    public int CountOfSubstrings(string word, int k)
    {
        int retVal = 0;

        for (int i = 0; i < word.Length; i++)
        {
            HashSet hsVowels = new HashSet();
            string vowels = "aeiou";
            int count = k;

            for (int j = i; j < word.Length; j++)
            {
                if (vowels.Contains(word[j]))
                {
                    if (!hsVowels.Contains(word[j]))
                        hsVowels.Add(word[j]);
                }
                else count--;

                if (hsVowels.Count == vowels.Length && count == 0)
                    retVal++;

                if (count < 0) break;
            }
        }

        return retVal;
    }
}