题目内容
给定一个字符串，求字符串的满足要求的最长子串的长度。要求子串中每个字符重复出现次数>=k。
样例
输入:
s = "ababbc", k = 2
输出:
5
最长合法子串是 "ababb", 其中'a'出现了2次，'b'出现了3次
解法1 归并
首先考虑整个字符串，计算每个字符出现的次数，如果某个字符在整个字符串中出现次数<k，说明这个字符是非法字符，一定不会出现在最后的合法子串中。
例如s = 'bbcamabab', k = 2，发现m和c只出现1次，因此字符m和c不可能出现在合法子串中，由于子串要求是连续子串，因此以非法字符隔开，得到'bb|a|abab',合法子串只可能出现在||隔出来的区域中
因此问题就可以缩小成子问题，即求被隔出来的’bb’, ‘a’, ‘abab’中的合法子串的最大值。而当所求的子问题足够小，即字符串s本身长度小于k，那么不可能存在合法子串，返回0即可。
复杂度分析
由于s的每次拆分成子问题时，都会减少一个不合法的字符（即出现次数<k的字符），而s中只包含小写字母，因此最多拆分26次。而处理子问题需要求出每个字符出现次数，为O(N)的复杂度，因此时间复杂度为O(26N)。
from collections import Counter
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
if len(s) < k:
return 0
counter = Counter(s)
max_len = 0
last_pos = 0 # 用于计算divide的子问题的区间
find_invalid_c = False # 是否发现出现次数<k的字符
for i in range(len(s)):
if counter[s[i]] < k:
# 说明这个字符肯定不能出现在结果的子串里
find_invalid_c = True
l = self.longestSubstring(s[last_pos:i], k) # 即对被||隔出来的子区间进行求解
max_len = max(max_len, l)
last_pos = i + 1
if not find_invalid_c: # 说明s中所有字符出现次数都>=k了
return len(s)
max_len = max(max_len, self.longestSubstring(s[last_pos:], k)) # 对最后一个区间进行求解
return max_len
解法2 双指针 滑动窗口
看到最长/最短满足条件的合法子串，通用的做法是双指针滑动窗口求解。滑动窗口的解法的思路就是不断移动右指针，当发现满足条件后，移动左指针寻找最大/最小满足条件的区间。但是这题不具有单调性，不能直接应用滑动窗口求解。
我们可以对这个问题加一个约束，即限定子串中有l个不同的字符，这样问题就变成了Longest Substring with At Most K Distinct Characters，只需要将合法条件修改一下即可。
复杂度分析
滑动窗口复杂度为O(N)，枚举包含不同字符个数，有26种情况，因此复杂度为O(26N)
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
max_len = 0
for l in range(1, 27): # 枚举子串包含多少个不同的字符
counter = {}
left = 0
for i in range(len(s)):
if s[i] not in counter:
counter[s[i]] = 0
counter[s[i]] += 1
while len(counter) > l: # 移动左指针，找最长的合法区间
counter[s[left]] -= 1
if counter[s[left]] == 0:
del counter[s[left]]
left += 1
if len(counter) == l: # 此时区间有l个不同的字符，判断是否满足每个字符都至少出现k次
valid = True
for c in counter:
if counter[c] < k and counter[c] > 0:
valid = False
if valid:
max_len = max(max_len, i - left + 1)
return max_len
