Leetcode 395.至少有K个重复字符的最长子串 2021.02.27

Leetcode 395.至少有K个重复字符的最长子串 2021.02.27

二月 27, 2021

395. 至少有 K 个重复字符的最长子串

  • 难度：中等

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例

示例1：

输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。

示例2：

输入：s = “ababbc”, k = 2
输出：5
解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。

说明

  • 1 <= s.length <= 104
  • s 仅由小写英文字母组成
  • 1 <= k <= 105

思路

  • 滑动窗口+双指针

    charType为假设的字符种类数

    charHash为哈希数组

    less为不足k的字符种类数

    typeTotal为当前哈希数组内的字符种类数

    1. 首先我们假设最长字串仅有一个字符符合题目要求，逐步增加，直至假设26个字符都符合题目
    2. 接着我们用左、右双指针指向字符串的头
    3. 如果右指针未到字符串的尾部
      1. 把右指针指向的字符加进一个哈希数组里
        1. 如果哈希数组对应字符的值为1，说明刚才这个值是新加进去的，刚才并没有这个值，则less、typeTotal均加1
        2. 如果哈希数组对应字符的值为k，说明这个数达到k的要求了，less就能减1
      2. 如果当前哈希数组内的字符种类数超出我们假设的字符种类数，我们便把左指针指向的字符从哈希数组中减去，直至typeTotal≤charType
        1. 如果哈希数组对应字符的值为k-1，说明这个字符刚才符合k的要求，现在缺不符合了，less需要加1
        2. 如果哈希数组对应字符的值为0，说明这个字符现在不存在我们的窗口内了，less、typeTotal均需要减1
        3. 左移左指针
      3. 当less等于0，说明窗口内的字符符合题目要求，与以往的字串比较，取最长的。
      4. 左移右指针

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int longestSubstring(string s, int k) {
    int res = 0;
    
    //假设最长窗口内包含的不同字符种类
    for(int charType = 1;charType <= 26;charType++){
        int l = 0;//左指针
        int r = 0;//右指针
        vector<int> charHash(26, 0);//哈希数组
        int less = 0;//不符合k个字符的字符种类数
        int typeTotal = 0;//窗口内包含的字符种类数

        //直至右指针直到字符串结尾
        while(r < s.length()){
            //右指针指向的字符存取哈希数组中
        	charHash[s[r] - 'a']++;
            
            //判断字符对应哈希数组的数组是否等于1，等于1说明刚才并没有这个字符种类
            if(charHash[s[r] - 'a'] == 1){
                less++;//不足k个字符种类数加1
                typeTotal++;//窗口内的字符种类数加1
            }
            
            //判断字符对应哈希数组的数组是否等于K，等于K说明刚才并没有符合k个字符的要求
            if(charHash[s[r] - 'a'] == k){
                less--;//现在符合了，不足k个字符种类数减1
            }
            
            //直至窗口内的字符种类数少于我们假设的字符数
            while(typeTotal > charType){
                //减去哈希数组中左指针指向的字符
                charHash[s[l] - 'a']--;
                
                //判断字符对应哈希数组的数组是否等于K-1，等于K-1说明刚才符合k个字符的要求
                if(charHash[s[l] - 'a'] == k-1){
                    less++;//现在不符合了，不足k个字符种类数加1
                }
                
                //判断字符对应哈希数组的数组是否等于0，等于0说明刚才存在这个字符
                if(charHash[s[l] - 'a'] ==  0){
                    typeTotal--;//窗口内的字符种类数减1
                    less--;//现在这个字符不存在了，不足k个字符种类数减1
                }
                
                l++;//右移左指针
            }
            
            //less为零说明窗口内的字符串符合题目要求
            if(less == 0){
                res = max(res,r-l+1);//与以往的结果比较，取最大值
            }
            
            r++;//右移右指针
        }
    }
    return res;
}
  1. 1. 395. 至少有 K 个重复字符的最长子串
  2. 2. 示例
  3. 3. 说明
  4. 4. 思路
  5. 5. 代码实现