3297. 统计重新排列后包含另一个字符串的子字符串数目 I

思路

滑动窗口，枚举右端点，对于每个右端点，当前有多少个合法的左端点，就是以当前右端点结尾的合法子串个数。

代码

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        long long ans=0;
        unordered_map<char,int>mp;
        int n=word1.size(),m=word2.size();
        int cnt=0;
        for(int i=0;i<m;i++){
            mp[word2[i]]++;

        }
        int val=0;
        int left=0;

        for(int right=0;right<n;right++){
            if(mp.contains(word1[right])){
                mp[word1[right]]--;
                if(mp[word1[right]]==0){
                    cnt++;
                }
            }
            cout<<val<<endl;
            while(cnt==mp.size()){
                val++;
                if(mp.contains(word1[left])){
                    mp[word1[left]]++;
                    if(mp[word1[left]]>0){
                        cnt--;
                    }
                }
                left++;
                
            }
            ans+=val;
            
        }
        return ans;
    }
};