3570. Count Of Substrings Containing Every Vowel And K Consonants I¶

3570. 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

Solution¶

class Solution {
    public int countOfSubstrings(String word, int k) {
        int n = word.length();
        int answer = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            for (int j = i; j < n; j++) {
                char current = word.charAt(j);
                if (isVowel(current)) {
                    map.put(current, map.getOrDefault(current, 0) + 1);
                }   
                else count++;
                if (compute(map) == true && count == k) {
                    answer++;
                }
            }
        }
        return answer;
    }

    private boolean compute(HashMap<Character, Integer> map) {
        int count = 0;
        if (map.getOrDefault('a' , 0) > 0) count++;
        if (map.getOrDefault('e' , 0) > 0) count++;
        if (map.getOrDefault('i' , 0) > 0) count++;
        if (map.getOrDefault('o' , 0) > 0) count++;
        if (map.getOrDefault('u' , 0) > 0) count++;
        return count == 5;        
    }

    private boolean isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]