题目

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

示例：

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

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

提示：

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

解答 & 代码

滑动窗口

时间复杂度，N 是数组长度，|Σ| 是字符集长度，外层循环枚举 |Σ| 次。内层循环滑动窗口的复杂度为 N ，初始化 winChCnt 数组的复杂度为 |Σ|

空间复杂度为 O(|Σ|)

class Solution {
public:
  int longestSubstring(string s, int k) {
      int sLen = s.size();
      if(sLen < 1 || k > sLen)    // 特殊情况
          return 0;

      int maxSubLen = 0;            // 符合条件的最长子串（窗口）长度
      // 枚举滑动窗口中可以包含的字符种数（因为 s 仅由小写字符构成，因此种数可为 1- 26）
      for(int chTypes = 1; chTypes <= 26; ++chTypes)
      {
          if(chTypes > sLen)        // 如果窗口可包含的字符种数大于字符串 s 的长度，不可能存在
              break;

          int left = 0;            // 窗口左边界
          int right = 0;            // 窗口右边界
          vector<int> winChCnt(26, 0);    // 数组，存储窗口中各个字符出现的次数
          int winChType = 0;                // 窗口中出现的字符种数
          int winLessKChType = 0;            // 窗口中出现次数小于 k 的字符种数
          // 滑动窗口
          while(left < sLen && right < sLen)
          {
              winChCnt[s[right] - 'a'] += 1;        // 右边界对应的字符次数 +1
              if(winChCnt[s[right] - 'a'] == 1)    // 如果该字符是新出现的
              {
                  ++winChType;                    // 窗口中出现的字符数 +1
                  ++winLessKChType;                // 窗口中出现次数小于 k 的字符种数 +1
              }
              if(winChCnt[s[right] - 'a'] == k)    // 如果该字符出现的次数达到了 k
                  --winLessKChType;                // 窗口中出现次数小于 k 的字符种数 -1

              // 如果窗口中出现的字符种数大于 chTypes，则左边界右移
              while(winChType > chTypes && left < sLen)
              {
                  winChCnt[s[left] - 'a'] -= 1;
                  if(winChCnt[s[left] - 'a'] == 0)
                  {
                      --winChType;
                      --winLessKChType;
                  }                        
                  if(winChCnt[s[left] - 'a'] == k - 1)
                      ++winLessKChType;
                  ++left;
              }

              // 如果窗口中出现次数小于 k 的字符种数为 0，更新最长子串的长度
              if(winLessKChType == 0 && right - left + 1 > maxSubLen)
                  maxSubLen = right - left + 1;

              // 右边界右移
              ++right;
          }
      }
      return maxSubLen;
  }
};

执行结果： ``` 执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 36.00% 的用户内存消耗：6.1 MB, 在所有 C++ 提交中击败了 96.23% 的用户 ```

CodeTop 企业题库

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

题目

解答 & 代码