【Leetcode Daily】3325字符至少出现K次的子字符串

题目浅析

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

• 简单地说，就是给一个小写字母字符串以及一个数字 K，要求给出其中所有子字符串，每个字符串至少有一个字母的个数不小于 K。

思路分享

• 越长越合法类型的不定长滑动窗口（【Leetcode Daily】1358包含所有三种字符的子字符串数目）

• 这里就稍微再解释下所谓的“越长越合法”罢，毕竟也是今天看了题解，突然有所感悟。这句话就是所得答案长度越长的情况下，往往是合法的。拿本题第一个输入举例。

• 输入：“s = “abacb”, k = 2”；输出：“4”

• 如果窗口内现在是 aba，那么肯定是符合条件的，所以窗口左部滑动后，窗口内容变成 ba，在下一循环变成 bac 时，答案也加上一，原因就是“越长越合法”，即把之前合法的情况和现在的窗口拼一起算上了。

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

• 参考题解

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int ans = 0, left = 0;
        int rec[26]{};
        for (int right = 0; right < s.size(); right++) {
            rec[s[right]-'a']++;
            while (rec[s[right]-'a']==k) {
                rec[s[left++]-'a']--;
            }
            //cout << left << " " << right << endl;
            ans += left;
        }
        return ans;
    }
};