【Leetcode Daily】3298统计重新排列后包含另一个字符串的子字符串数目II

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给两个字符串，记作 s1 和 s2，求包含 s2 的 s1 字符串数目。所谓的包含是指 s2 各个字母数量不多于子串。

思路分享

• 虽说是 hard 题，但只要知道是越长越合法的不定长滑动窗口类型，就能轻松解决。总体上思路同【Leetcode Daily】2799统计完全子数组的数目。

• 简单说下参照灵神题解后的改进，原来是直接对比26个字母是否都大于，虽然复杂度也是 O(n)，但时间耗费肯定大些，好在数组效率高还是 ac 了。要更快些，可以设立单独的变量记录包含字母的个数，条件就直接判断该变量是否满足条件即可。

  https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/solutions/2925828/on-hua-dong-chuang-kou-qiu-ge-shu-python-0x7a/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        int rec1[26]{}, rec2[26]{};
        for (const char &c : word1) {
            rec1[c-'a']++;
        }
        for (const char &c : word2) {
            rec2[c-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (rec2[i] > rec1[i]) return 0;
        }

        long long left = 0, ans = 0;
        int less = 0;
        for (const int &i : rec2) {
            less += (i>0);
        }
        int rec[26] {};
        for (int right = 0; right < word1.size(); right++) {
            int index = word1[right]-'a';
            rec[index]++;
            if (rec[index] == rec2[index]) less--;
            while(less == 0) {
                if (rec[word1[left]-'a']==rec2[word1[left]-'a']) less++;
                rec[word1[left++]-'a']--;
            }
            ans += left;
        }

        return ans;
    }
};

/*
class Solution {
public:
    bool contain(const int *rec1, const int *rec2) {
        for (int i = 0; i < 26; i++) {
            if (rec2[i] > rec1[i]) return false;
        }
        return true;
    }
    long long validSubstringCount(string word1, string word2) {
        int rec1[26]{}, rec2[26]{};
        for (const char &c : word1) {
            rec1[c-'a']++;
        }
        for (const char &c : word2) {
            rec2[c-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (rec2[i] > rec1[i]) return 0;
        }

        long long left = 0, ans = 0;
        int rec[26] {};
        for (int right = 0; right < word1.size(); right++) {
            rec[word1[right]-'a']++;
            while(contain(rec, rec2)) {
                rec[word1[left++]-'a']--;
            }
            ans += left;
        }

        return ans;
    }
};
*/