前言:之前做的滑动窗口都是可以直接一遍过,然后每次右边确定了以后,左边不断缩小寻找最优解
但是这个题目呢我们不仅要保证我们的辅音字母的个数恰好为k,其他元音字母的个数只要每个都出现了就行,这个就导致我们不能用正常的思路来考虑这个问题
我们可以转换为最多,最少的问题,我们可以转换为
辅音字母至少为k+1 - 至少为 k 个
class Solution {
public:long long countOfSubstrings(string word, int k) {return fun(word,k)-fun(word,k+1);}long long fun(string word,int k){set<int> s; s.insert('a'); s.insert('e'); s.insert('i'); s.insert('o'); s.insert('u');map<int,int> mp;int l=0;int num1 =0,num2 = 0;long long ans = 0;for(int r=0;r<word.size();r++){int u = word[r];if(s.contains(u)){mp[u]++;if(mp[u]==1){num1++;}}else{num2++;}while(num1==5&&num2>=k){int u = word[l];if(s.contains(u)){mp[u]--;if(mp[u]==0) num1--;}else{num2--;}l++;}ans += l;}return ans;}
};
这里有一个细节,就是我们的每次循环都会加上我们的左端点,因为我们的右端点在扩展的时候,即使是一些无效扩展,我们每次前面计算的答案都是合法的