0395. 至少有 K 个重复字符的最长子串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 分治

1. 📝 题目描述

• leetcode

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

如果不存在这样的子字符串，则返回 0。

---

示例 1：

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

示例 2：

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

---

提示：

• 1 <= s.length <= 10^4
• s 仅由小写英文字母组成
• 1 <= k <= 10^5

2. 🎯 s.1 - 分治

c

int longestSubstring(char* s, int k) {
    int len = strlen(s);
    if (len < k) return 0;
    int count[26] = {0};
    for (int i = 0; i < len; i++) count[s[i] - 'a']++;
    for (int i = 0; i < len; i++) {
        if (count[s[i] - 'a'] < k) {
            // 按该字符分割
            int maxLen = 0;
            int start = 0;
            for (int j = 0; j <= len; j++) {
                if (j == len || s[j] == s[i]) {
                    if (j > start) {
                        char tmp = s[j]; s[j] = '\0';
                        int sub = longestSubstring(s + start, k);
                        if (sub > maxLen) maxLen = sub;
                        s[j] = tmp;
                    }
                    start = j + 1;
                }
            }
            return maxLen;
        }
    }
    return len;
}

js

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstring = function (s, k) {
  if (s.length < k) return 0
  const count = new Map()
  for (const ch of s) count.set(ch, (count.get(ch) || 0) + 1)
  for (const [ch, freq] of count) {
    if (freq < k) {
      return Math.max(...s.split(ch).map((sub) => longestSubstring(sub, k)))
    }
  }
  return s.length
}

py

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0
        for ch in set(s):
            if s.count(ch) < k:
                return max(self.longestSubstring(sub, k) for sub in s.split(ch))
        return len(s)

• 时间复杂度：$O(26\cdot n)$，最多递归 26 层
• 空间复杂度：$O({26}^2)$，递归栈

算法思路：

• 找到出现次数小于 $k$ 的字符，按该字符分割字符串
• 对每个子串递归求解，取最大值
• 若所有字符块达标则返回字符串长度