【力扣刷题】3305. 元音辅音字符串计数 I-滑动窗口

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

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

示例 1：

示例 2：

示例 3：

提示：

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

自己的解法：

class Solution {
public:
    int countOfSubstrings(string word, int k) {
        unordered_map<char,int>mp;
        mp['a']=mp['e']=mp['i']=mp['o']=mp['u']=1;
        int l=0,window=k,r=0;
        int res=0;
        while(l<=word.size()-1-k){
            int cnt=0;bool flag=1;
            r=l+window;
            if(r>word.size()-1){
                l++;
                window=k;
                r=l+window;
            }
            if(l>word.size()-1-k)break;
            // cout<<l<<" "<<r<<" "<<window<<endl;
            for(int i=l;i<=r;i++){
                // cout<<word[i];
                if(!mp[word[i]]&&word[i]!='a'&&word[i]!='e'&&word[i]!='i'&&word[i]!='o'&&word[i]!='u'){
                    cnt++;
                }else{
                    mp[word[i]]=0;
                }
            }
            // cout<<endl;
            if(mp['a']||mp['e']||mp['i']||mp['o']||mp['u'])flag=0;
            // cout<<"flag="<<flag<<" cnt="<<cnt<<endl;
            if(flag){
                if(cnt==k){
                    res++,window++;
                }else if(cnt<k){
                    window++;
                }else{
                    l++;window=k;
                }
            }else{
                window++;
            }
            cnt=0,flag=1;
            mp['a']=mp['e']=mp['i']=mp['o']=mp['u']=1;
        }
        return res;
    }
};

很好的题解：

class Solution {
public:
    const string VOWEL="aeiou";
    long long f(string& word, int k){
        long long ans=0;
        unordered_map<int,int>mp;//元音数目
        int cnt=0;//辅音数目
        int l=0;
        for(char x:word){
            if(VOWEL.find(x)!=string::npos){
                mp[x]++;
            }else{
                cnt++;
            }
            while(mp.size()==5&&cnt>=k){
                char x=word[l];
                if(VOWEL.find(x)!=string::npos){
                    mp[x]--;
                    if(mp[x]==0)mp.erase(x);
                }else{
                    cnt--;
                }
                l++;
            }
            ans+=l; //右端点固定在 right，左端点在 0,1,2,⋯,left−1 的所有子串都是合法的，这一共有 left 个。
        }
        return ans;
    }

    long long countOfSubstrings(string word, int k) {
        // 将“恰好为k个”问题转化为“至少k个”-“至少k+1个”
        return f(word,k)-f(word,k+1);
    }
};