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

SourceWeekly Contest 417 Q2DifficultyMediumRating1563

Description

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

Solutions

Solution 1: Problem Transformation + Sliding Window

Thinking

With \(|\textit{word}| \le 250\), enumerating substrings works, but a window that must contain every vowel and exactly \(k\) consonants is not monotone in a single constraint.

We rewrite “exactly \(k\) consonants” as \(f(k)-f(k+1)\), where \(f(t)\) counts substrings with all five vowels and at least \(t\) consonants. The “at least” form lets the left pointer advance whenever the window is valid.

Every substring ending at the current right end and starting in \([0, l)\) is then valid, so we add \(l\). A map tracks the five vowels; consonants use a separate counter \(x\).

We can transform the problem into solving the following two subproblems:

Find the total number of substrings where each vowel appears at least once and contains at least \(k\) consonants, denoted as \(\textit{f}(k)\);
Find the total number of substrings where each vowel appears at least once and contains at least \(k + 1\) consonants, denoted as \(\textit{f}(k + 1)\).

Then the answer is \(\textit{f}(k) - \textit{f}(k + 1)\).

Therefore, we design a function \(\textit{f}(k)\) to count the total number of substrings where each vowel appears at least once and contains at least \(k\) consonants.

We can use a hash table \(\textit{cnt}\) to count the occurrences of each vowel, a variable \(\textit{ans}\) to store the answer, a variable \(\textit{l}\) to record the left boundary of the sliding window, and a variable \(\textit{x}\) to record the number of consonants in the current window.

Traverse the string. If the current character is a vowel, add it to the hash table \(\textit{cnt}\); otherwise, increment \(\textit{x}\) by one. If \(\textit{x} \ge k\) and the size of the hash table \(\textit{cnt}\) is \(5\), it means the current window meets the conditions. We then move the left boundary in a loop until the window no longer meets the conditions. At this point, all substrings ending at the right boundary \(\textit{r}\) and with the left boundary in the range \([0, .. \textit{l} - 1]\) meet the conditions, totaling \(\textit{l}\) substrings. We add \(\textit{l}\) to the answer. Continue traversing the string until the end, and we get \(\textit{f}(k)\).

Finally, we return \(\textit{f}(k) - \textit{f}(k + 1)\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{word}\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        def f(k: int) -> int:
            cnt = Counter()
            ans = l = x = 0
            for c in word:
                if c in "aeiou":
                    cnt[c] += 1
                else:
                    x += 1
                while x >= k and len(cnt) == 5:
                    d = word[l]
                    if d in "aeiou":
                        cnt[d] -= 1
                        if cnt[d] == 0:
                            cnt.pop(d)
                    else:
                        x -= 1
                    l += 1
                ans += l
            return ans

        return f(k) - f(k + 1)

class Solution {
    public int countOfSubstrings(String word, int k) {
        return f(word, k) - f(word, k + 1);
    }

    private int f(String word, int k) {
        int ans = 0;
        int l = 0, x = 0;
        Map<Character, Integer> cnt = new HashMap<>(5);
        for (char c : word.toCharArray()) {
            if (vowel(c)) {
                cnt.merge(c, 1, Integer::sum);
            } else {
                ++x;
            }
            while (x >= k && cnt.size() == 5) {
                char d = word.charAt(l++);
                if (vowel(d)) {
                    if (cnt.merge(d, -1, Integer::sum) == 0) {
                        cnt.remove(d);
                    }
                } else {
                    --x;
                }
            }
            ans += l;
        }
        return ans;
    }

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

class Solution {
public:
    int countOfSubstrings(string word, int k) {
        auto f = [&](int k) -> int {
            int ans = 0;
            int l = 0, x = 0;
            unordered_map<char, int> cnt;
            auto vowel = [&](char c) -> bool {
                return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
            };
            for (char c : word) {
                if (vowel(c)) {
                    cnt[c]++;
                } else {
                    ++x;
                }
                while (x >= k && cnt.size() == 5) {
                    char d = word[l++];
                    if (vowel(d)) {
                        if (--cnt[d] == 0) {
                            cnt.erase(d);
                        }
                    } else {
                        --x;
                    }
                }
                ans += l;
            }
            return ans;
        };

        return f(k) - f(k + 1);
    }
};

func countOfSubstrings(word string, k int) int {
    f := func(k int) int {
        var ans int = 0
        l, x := 0, 0
        cnt := make(map[rune]int)
        vowel := func(c rune) bool {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
        }
        for _, c := range word {
            if vowel(c) {
                cnt[c]++
            } else {
                x++
            }
            for x >= k && len(cnt) == 5 {
                d := rune(word[l])
                l++
                if vowel(d) {
                    cnt[d]--
                    if cnt[d] == 0 {
                        delete(cnt, d)
                    }
                } else {
                    x--
                }
            }
            ans += l
        }
        return ans
    }

    return f(k) - f(k+1)
}

function countOfSubstrings(word: string, k: number): number {
    const f = (k: number): number => {
        let ans = 0;
        let l = 0,
            x = 0;
        const cnt = new Map<string, number>();

        const vowel = (c: string): boolean => {
            return c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u';
        };

        for (const c of word) {
            if (vowel(c)) {
                cnt.set(c, (cnt.get(c) || 0) + 1);
            } else {
                x++;
            }

            while (x >= k && cnt.size === 5) {
                const d = word[l++];
                if (vowel(d)) {
                    cnt.set(d, cnt.get(d)! - 1);
                    if (cnt.get(d) === 0) {
                        cnt.delete(d);
                    }
                } else {
                    x--;
                }
            }
            ans += l;
        }

        return ans;
    };

    return f(k) - f(k + 1);
}

impl Solution {
    pub fn count_of_substrings(word: String, k: i32) -> i32 {
        fn f(word: &Vec<char>, k: i32) -> i32 {
            let mut ans = 0;
            let mut l = 0;
            let mut x = 0;
            let mut cnt = std::collections::HashMap::new();

            let is_vowel = |c: char| matches!(c, 'a' | 'e' | 'i' | 'o' | 'u');

            for (r, &c) in word.iter().enumerate() {
                if is_vowel(c) {
                    *cnt.entry(c).or_insert(0) += 1;
                } else {
                    x += 1;
                }

                while x >= k && cnt.len() == 5 {
                    let d = word[l];
                    l += 1;
                    if is_vowel(d) {
                        let count = cnt.entry(d).or_insert(0);
                        *count -= 1;
                        if *count == 0 {
                            cnt.remove(&d);
                        }
                    } else {
                        x -= 1;
                    }
                }
                ans += l as i32;
            }
            ans
        }

        let chars: Vec<char> = word.chars().collect();
        f(&chars, k) - f(&chars, k + 1)
    }
}

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

Description

Solutions

Solution 1: Problem Transformation + Sliding Window

Comments