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

题目链接：395. 至少有 K 个重复字符的最长子串

题目描述

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

核心思考：分治法与寻找“越界断点”

如果按照常规的滑动窗口思路，本题会变得异常棘手。因为我们既不知道窗口内允许包含多少种不同的字符，也不能在某个字符个数“暂不达标”时立刻断定窗口必须收缩（由于可能继续向右扩展而满足条件，这违背了滑动窗口条件单调性的基建核心）。

打破僵局的点在于放眼全局的逆向切分（也就是分治算法的核心体现）。

降维打击的劈裂逻辑

思考一个极度根本的客观事实：如果某个字符在整个母字符串 s 中的出现总频率都硬性不足 k 次，那么它绝对不可能、也绝不能被包裹在符合最终规定的目标子串内。

基于这个不可违背的物理边界，我们可以将这个不合格的字符提炼为完美的天然断点（Splitter）：

1. 边界剪枝：如果传进来的字符串长度连题干要求的下限 k 都不足了，显然无法满足，直接抛弃并返回 0。
2. 定位断点与降维裂断：对当前字符串 s 中的字符进行去重探测（通过 set 降维）。一旦揪出任何总数不达标（<k）的字母，它就像一道不可跨越的鸿沟。所以，我们直接以此字母作为劈裂刀，将原始的主串 s 大刀阔斧地利用 split(char) 劈分成若干个互不相连的子片段。
3. 递归探底与回溯求极值：主串被劈裂后产生的那些子片段是否安全？同样不得而知。于是顺理成章地将它们原路倒灌回主求解函数进行递归（Recursion），分而治之地索要它们内部产生的最大合格子串长度，最后比对提取极大值返回 max(...) 即可。
4. 递归的平底大基座：如果遍历完这套 set(s) 集合，发现所有的字母出现次数都极其坚挺地大于或等于了警戒线 k，说明这整个入参字符串完全无懈可击！它是完美的，那么我们就可以堂堂正正地原位交还它的总体长度 len(s)。

这种不断基于弱项实行切割分离的战术非常惊艳，完美避开了穷举的性能灾难。

解题思路 (Python)

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0
        for char in set(s):
            if s.count(char) < k:
                return max(self.longestSubstring(other,k) for other in s.split(char))
        # 未进入递归说明所有出现的字符都大于k次了
        return len(s)

复杂度分析

• 时间复杂度：$O(N \cdot |\Sigma|)$，其中 $N$ 是主串 s 的长度，$|\Sigma|$ 代表英文字母符号集的大小（最大为 26 个）。在极端的递归雪崩状态下，字符最多会产生 $|\Sigma|$ 层的二叉切分，而每一次子状态扫描（count() 及 split() 均触及底层遍历）又与当切分深度下的主字符串分布规模呈全局准线性相关。
• 空间复杂度：$O(|\Sigma|)$。虽然并未使用庞大且显式的图级状态记忆变量，但随递归向内切分必然连带深达 $|\Sigma|$ 的调用栈消耗堆叠，系统将承接这层额外的隐藏空间花销。