题目

题目来源：力扣（LeetCode）

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

示例 1：

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

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

思路分析

对于字符串 s，如果存在某个字符 ch，它的出现次数大于 0 且小于 k，则任何包含 ch 的子串都不可能满足要求。那么我们将字符串按照 ch 切分成若干段，则满足要求的最长子串一定出现在某个被切分的段内，而不能跨越一个或多个段。因此，可以考虑分治的方式求解本题。

算法

  1. 遍历字符串统计所有字符出现的次数
  2. 遍历所有字符，找到出现次数小于 k 的字符，以当前字符为分割点，将字符串 s 切分成若干个子串
  3. 继续对子串执行步骤1 和步骤2，找出符合要求的最长子串

举个简单例子:
假设字符串 str = “eaaabcbcbcdeeeee”, k = 3的时候, 各个字符出现频率为:
a:3, b:3, c:3, d:1, e: 5

由于 d 出现的次数小于 k，因此用 d 作为切割点, 将字符串分割为两个子串然后再对子串进行查找:

str1 = “aaabcbcbc”, 子串 str1 中的每个字符出现的次数都大于等于 k，符合要求
str2 = “eeeee”, 子串 str2 中的字符出现的次数大于 k，符合要求，但由于其长度为 5，小于子串 str1 的长度 9， str2 不是最长子串，因此 str2 不是最优解。

代码

  1. /**
  2.  * @param {string} s
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var longestSubstring = function (s, k) {
  7.   const n = s.length;
  8.   // 对原始字符串s的切割过程
  9.   return dfs(s, k);
  10. }
  11. // 对字符串进行tokenize，每个片段重复计算是否满足要求
  12. const dfs = (s, k) => {
  13.   if (!s) return 0;
  14.   const cnt = new Array(26).fill(0);
  15.   // 统计当前片段中字符出现的次数
  16.   for (const ch of s) {
  17.     cnt[ch.charCodeAt() - 'a'.charCodeAt()]++;
  18.   }
  19.   // 遍历所有字符 
  20.   for (let i = 0; i < 26; i++) {
  21.     if (cnt[i] && cnt[i] < k) {
  22.       // 当前字符出现的次数小于 k，那么任何包含当前字符的 子串都不满足要求，按照当前字符将字符串切分成若干段
  23.       const subStrings = s.split(String.fromCharCode(i + 'a'.charCodeAt()))
  24.       // 最后答案的字符串的长度
  25.       let ret = 0;
  26.       // 遍历切分后的子串
  27.       for (const subString of subStrings) {
  28.         // 递归求解符合要求的子串
  29.         const len = dfs(subString, k)
  30.         // 符合要求的最长子串
  31.         ret = Math.max(len, ret)
  32.       }
  33.       return ret;
  34.     }
  35.   }
  36.   // 如果每个字符都都满足大于 k，会走到此处，当前串满足条件，直接返回字符串长度即可
  37.   return s.length;
  38. };