哈希表分治

如何求至少有 K 个重复字符的最长子串？

• 频数表: 先统计整个字符串的字符频数;
• 分治依据: 频数小于 k 的字符一定不会出现在答案里;
• 切分: 用这些低频字符把字符串切开, 对每一段递归求解;
• 收敛: 若不存在低频字符, 说明整个字符串满足条件, 直接返回其长度;
• 边界: 段长小于 k 时不可能满足条件, 返回 0;
• 复杂度: 时间 O(n²) 最坏, 空间 O(n);

function longestSubstring(s: string, k: number): number {
  if (s.length < k) return 0;

  const hash = new Map<string, number>();
  for (const ch of s) hash.set(ch, (hash.get(ch) ?? 0) + 1);

  for (const [ch, count] of hash) {
    if (count >= k) continue;

    let result = 0;
    for (const part of s.split(ch)) {
      result = Math.max(result, longestSubstring(part, k));
    }
    return result;
  }

  return s.length;
}