统计完全子字符串

题目

2953. 统计完全子字符串

---

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

如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：

• s 中每个字符 恰好 出现 k 次。
• 相邻字符在字母表中的顺序 至多 相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差 至多 为 2 。

请你返回 word 中 完全 子字符串的数目。

子字符串 指的是一个字符串中一段连续 非空 的字符序列。

示例 1：

输入：word = "igigee", k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。

示例 2：

输入：word = "aaabbbccc", k = 3
输出：6
解释：完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。

提示：

• 1 <= word.length <= 10^5
• word 只包含小写英文字母。
• 1 <= k <= word.length

题解

方法一：

思路

相邻字符字典序相差至多为2，我们可将整个串分割成若干子串。对于每个子串满足相邻字符字典序相差至多为2。

对于子串s，我们进行$min(26, \lfloor\frac{|s|}{k}\rfloor)$次滑动窗口，第i次滑窗的固定滑动窗口大小为$i\times k$，在滑窗过程中检测窗口内恰好有i个字符出现k次则说明这个子串是合法子串。给答案贡献1。

代码

class Solution {
public:
    int countCompleteSubstrings(string word, int k) {
        auto sw = [&](string s) {
            int sz = s.size(), rt = 0;
            for (int i=1; i<=26 && i*k<=sz; i++) {
                vector<int> c(26);
                for (int r=0; r<sz; r++) {
                    c[s[r]-'a']++;
                    if (r-i*k>=0) c[s[r-i*k]-'a']--;
                    if (count(c.begin(), c.end(), k) == i) rt++;
                }
            }
            return rt;
        };
        int ans = 0;
        int n = word.size();
        for (int i=0; i<n;) {
            int p = i++;
            while (i<n && abs(word[i]-word[i-1])<=2) i++;
            ans += sw(word.substr(p, i-p));
        }
        return ans;
    }
};