题目描述

给你一个字符串 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 <= 2 * 10^5
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

算法

(双指针) $O(n)$

1. 将问题中恰好出现 $k$ 个辅音字母转为至少出现 $k$ 个辅音字母减去至少出现 $k + 1$ 个辅音字母。
2. 对于每个右端点 $r$，找到尽可能小的左端点 $l$，满足 $[0, r], [1, r], \dots, [l - 1, r]$ 都是满足所有元音字母至少出现一次，且至少有 $lim$ 个辅音字母。
3. 注意到 $l$ 随着 $r$ 增加而不减的，故可以使用双指针。

时间复杂度

• 双指针每个位置被访问两次，故时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

#define LL long long

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

        auto solve = [&](int lim) {
            int t = 0;
            int a, e, i, o, u;
            a = e = i = o = u = 0;

            LL res = 0;
            for (int l = 0, r = 0; r < n; r++) {
                if (word[r] == 'a') ++a;
                else if (word[r] == 'e') ++e;
                else if (word[r] == 'i') ++i;
                else if (word[r] == 'o') ++o;
                else if (word[r] == 'u') ++u;
                else ++t;

                while (a && e && i && o && u && t >= lim) {
                    if (word[l] == 'a') --a;
                    else if (word[l] == 'e') --e;
                    else if (word[l] == 'i') --i;
                    else if (word[l] == 'o') --o;
                    else if (word[l] == 'u') --u;
                    else --t;

                    ++l;
                }

                res += l;
            }

            return res;
        };

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