难度: Medium
给你一个字符串 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 <= 104s 仅由小写英文字母组成1 <= k <= 105运行时间: 40 ms
内存: 0.0 MB
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
# split at ch whose count<k
# put all ch in stack
stack = [s]
max_len = 0
while stack:
ss = stack.pop()
for c in set(ss):
if ss.count(c)<k:
stack = stack+ss.split(c)
break
else:
max_len = max(max_len,len(ss))
return max_len
这个题解采用了分治的思想。首先将字符串 s 放入栈中。然后不断从栈中取出子串，统计每个字符出现的次数。如果所有字符出现次数都不小于 k，则更新目前为止找到的最长子串长度。否则，找到出现次数小于 k 的字符，以它为分隔符将子串分割成更短的子串，放入栈中继续处理。这样递归处理下去，直到栈为空，即可找到最长的满足条件的子串。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
# 栈初始时存放整个字符串
stack = [s]
max_len = 0
while stack:
ss = stack.pop()
# 检查当前子串每个字符的出现次数
for c in set(ss):
if ss.count(c) < k:
# 如果字符 c 出现次数小于 k，则以 c 为分隔符分割子串
stack = stack + ss.split(c)
break
else:
# 所有字符出现次数都不小于 k，更新最大长度
max_len = max(max_len, len(ss))
return max_len
在这个问题中，目标是找到所有字符都至少出现k次的最长子串。如果一个字符在某个子串中的出现次数小于k，那么这个字符不可能出现在满足条件的最长子串中。因此，以这些出现次数小于k的字符为分隔符分割字符串是合理的，因为它们标志着不可能属于有效子串的边界。这种分割方式帮助我们忽略那些不满足条件的部分，将问题缩小到更小的子串上，这是分治策略的核心。
实际上，每个子串可能会因为不同的字符而被多次分割和处理。题解中的表述可能有误，因为每个子串在被分割时，如果有多个不同的字符频率小于k，就会在每个这样的字符处被分割，从而产生新的子串。每个由这种方式产生的子串都会被单独处理。这确保了所有可能的子串都被考虑到，因为每次分割都是基于当前子串中不满足条件的字符进行的。
使用队列或链表代替栈在逻辑上是可行的，且可能改善程序的理解度。使用队列，将遵循先进先出的顺序，可能使得算法的执行更符合从原始字符串开始逐步细化的直观逻辑。而使用链表，可以灵活地在任意位置添加或删除子串，这可能有助于管理复杂的分割情况。每种数据结构的选择都依赖于具体实现的需求和性能优化。
是的，多个不同的字符频率小于k确实可能导致重复分割和处理，特别是当这些字符分布在不同位置时。为了优化这种情况，可以在分割前先对整个子串进行一次扫描，统计所有字符的出现次数，然后一次性去除所有出现次数小于k的字符。这样，每个子串在分割时可以减少重复的分割操作，从而提高效率。此外，使用一个高效的数据结构来维护字符计数，如哈希表，可以进一步提高处理速度。