题目描述
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入:
s = “aaabb”, k = 3
输出:
3
最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。
示例 2:
输入:
s = “ababbc”, k = 2
输出:
5
最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。
解题思路
使用分治法和递归来解决。对于某个字符，若其在当前串中出现次数小于 k，则该字符不会出现在最后的结果中，直接递归该字符左边和右边的串即可。
代码
Python 2.7.121
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
if k < 2:
return len(s)
def find(s, left, right, k):
if left > right:
return 0
hashmap = {}
for i in range(left, right + 1):
hashmap.setdefault(s[i], []).append(i)
for val in hashmap.values():
if len(val) > 0 and len(val) < k:
cur = val[0]
return max(find(s, left, cur - 1, k), find(s, cur + 1, right, k))
return right - left + 1
return find(s, 0, len(s) - 1, k)执行用时: 4232 ms内存消耗: 522.7 MB