[M滑动窗口] lc3305、lc3306. 元音辅音字符串计数 I、II(恰好型滑动窗口+双指针+思维+代码实现)

1. 题目来源

链接：3306. 元音辅音字符串计数 II

2. 题目解析

思路：

• 恰好类型的问题，有个非常常用且重要的思维转换。
• 恰好 k 个 = 至少 k 个 - 至少 k+1 个
• 故，只需要实现找到在满足元音字母都出现的情况喜爱，至少有 k 个辅音字母计数过程即可。
• 考虑字符串子串 i~j 这个区间，出现了所有的元音字母，同时至少有 k 个辅音字母。那么 j+1，j+2，j+3 ，，，n 这些都是至少有 k 个辅音字母的可选答案。
• 故，对于每一个左指针 i 来说，我们应该找到第一个满足条件的右指针 j，并将答案类加上 n-j+1 这个后续的字符串。
• 且 i、j 是同向移动的，不会出现 j 回退的情况。这就是一个很基本的同向双指针滑动窗口的问题了。
• 同时注意优雅的代码实现，可以学习下 蛙佬 的代码。很是简洁，风格也相近。

---

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

代码：

class Solution {
public:long long countOfSubstrings(string word, int k) {typedef long long LL;LL res = 0;auto check = [&](char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';};auto get = [&](int K) {LL ans = 0;int cnt[26] = {0};int a = 0, b = 0;int n = word.size();// 同向滑动窗口for (int i = 0, j = 0; i < n; i ++ ) { // 基于每个 i，看所能到达的 j 最近是在哪里while (j < word.size() && (a < 5 || b < K)) {   // 右指针先向后拓展到最近的合法位置if (check(word[j])) {int t = cnt[word[j] - 'a'] ++ ;if (t == 0) a ++ ;} else b ++ ;j ++ ;}// 判断当前 i、j 区间是否是合法答案，则后续的 j+1,j+2,..,n 都是合法的// 这个判断还是需要的，不然当 j == n 的时候，虽然不构成答案，但还是+1，就构成了错误答案if (a == 5 && b >= K) ans += n - j + 1;// i 指针右移，处理 i 位置的字符if (check(word[i])) {int t = --cnt[word[i] - 'a'];if (t == 0) a -- ;} else b -- ;}return ans;};return get(k) - get(k + 1);}
};