题目描述

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

样例

输入：word = "aeioqq", k = 1

输出：0

解释：

不存在包含所有元音字母的子字符串。

输入：word = "aeiou", k = 0

输出：1

解释：

唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

输入：word = "ieaouqqieaouqq", k = 1

输出：3

解释：

包含所有元音字母并且恰好含有一个辅音字母的子字符串有：

word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。

限制

• 5 <= word.length <= 250
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

算法

(暴力枚举) $O(n^2)$

1. 枚举子字符串的左端点。
2. 枚举每个左端点对应的右端点，过程中记录当前子串中是否有所有的元音字母，以及辅音字母的个数。
3. 如果当前子串符合答案，则累加答案。

时间复杂度

• 遍历所有子串，故时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int countOfSubstrings(string word, int k) {
        const int n = word.size();

        int ans = 0;
        for (int l = 0; l < n; l++) {
            int t = 0;
            bool a, e, i, o, u;
            a = e = i = o = u = false;

            for (int r = l; r < n && t <= k; r++) {
                if (word[r] == 'a') a = true;
                else if (word[r] == 'e') e = true;
                else if (word[r] == 'i') i = true;
                else if (word[r] == 'o') o = true;
                else if (word[r] == 'u') u = true;
                else ++t;

                if (a && e && i && o && u && t == k)
                    ++ans;
            }
        }

        return ans;
    }
};