长度为 K 的重复字符子串

题意

给定一个字符串，问其中长度为k，且包含重复字符的字符串个数

方法

枚举起始位置

分析

我们对枚举每个位置作为起始位置

判断是否出现了重复字符，如果出现了则计数+1

则最后的计数总和就是要求的答案

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int numKLenSubstrRepeats(string s, int k) {
        int ans = 0;
        for(int i = 0;i + k <= s.length();i++){ // 枚举起始位置
            vector<int> cnt('z'-'a'+1,0); // 字符出现次数
            for(int j=0;j<k;j++){
                if(++cnt[s[i+j]-'a'] > 1){ // 出现次数大于1
                    ans ++;
                    break;
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 枚举了每个位置，每个位置遍历了长度，因为全部由小写字母组成，所以根据抽屉原理，长度超过26的必定存在相同字符串，所以总时间复杂度为$O(n\cdot min(27,k))O(n\backslash cdot\; min(27,k))$

空间复杂度: 用的额外空间是常数大小，所以空间复杂度为$O(1)O(1)$

双指针

分析

上面的方案，对于相邻的两个字符串来说，统计的部分重复了，而当一个字符串变成另一个字符串时

需要的变化是，增加尾部字符和去掉头部字符

我们这里关心的是是否有重复字符，换句话说出现次数大于1的字符有多少个

所以我们除了维护每个字符出现的次数以外，增加一个变量g1维护有多少个字符出现次数大于1

综上，步骤变为

1. 增加尾部字符，更新统计次数，如果让出现次数从1次变为2次，那么g1++
2. 删除头部字符，更新统计次数，如果让出现次数从2次变为1次，那么g1--

那么每次如果g1 > 0 则说明这个字符串有重复的字符

样例

以样例数据为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int numKLenSubstrRepeats(string s, int k) {
        vector<int> cnt('z'-'a'+1,0); // 出现个数
        int g1 = 0; // 比1大的个数
        int p0 = 0; // 字符串起始
        int ans = 0;
        for(int i = 0;i < s.length();i++){ // 结束的位置
            if(++cnt[s[i]-'a'] == 2){ // 个数从1变成2
                g1 ++;
            }
            if(i - p0 == k){ // 大于目标长度
                // 移除第一个
                if(--cnt[s[p0++]-'a'] == 1){ // 个数从2变成1
                    g1 --;
                }
            }
            if(i - p0 + 1 == k){ // 等于目标长度
                ans += g1 > 0; // 大于零则有重复字符
            }
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 只用了常数大小的额外空间，所以空间复杂度为$O(1)O(1)$

时间复杂度: 对于每个位置的操作是常数代价，所以总时间复杂度为$O(n)O(n)$