题解 | #长度为 K 的重复字符子串#

长度为K的重复字符子串

题目描述

给你一个由小写字母组成的长度为n的字符串 S ，找出所有长度为 k 且包含重复字符的子串，请你返回全部满足要求的子串的数目。

方法一：枚举法

解题思路

对于本题目的求解，使用枚举法，对每个位置进行枚举，判断是否出现了重复字符，如果出现了则计数加1，直到最后得到答案。

解题代码

class Solution {
public:
    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;//返回结果
    }
};

复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(n^2)O(n^2)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：双指针的方法

解题思路

基于方法一在维护每个字符出现的次数意外，我们增加一个变量来维护有多少个字符出现次数大于1。

解题代码

class Solution {
public:
    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(n)O(n)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$