题目
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
题意
给一个字符串s,求出该字符串中最长子串T，该T满足所有字符都大于等于K，返回T的长度。
例子
Input:
s = “ababbc”, k = 2
Output:
5
The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.
题解
分治的思路。首先遍历一遍统计各个字符出现频率。然后以那些字符个数小于k的字符为分界点，统计前半部分（从指针begin到end的部分）的字符是否存在满足条件的最长T（当他本身就满足时本身就是最长T），然后再以下一个字符为起点重复上述操作，最后求出最长T长度。
代码
func longestSubstring(s string, k int) int {
L := len(s)
if L==0{
return 0
}
hash:=make(map[byte]int)
for i,_:=range s{
hash[s[i]]++
}
fullString := true
for _,v:=range hash{
if v<k{
fullString = false
break
}
}
if fullString {
return L
}
begin,end,res := 0,0,0
for end<L{
if hash[s[end]]<k{
//递归统计前面部分字符的最长T长度。
res = Max(res,longestSubstring(s[begin:end],k))
begin = end+1
}
end++
}
res = Max(res,longestSubstring(s[begin:end],k))
return res
}
func Max(m1,m2 int) int{
if m1>m2{
return m1
}
return m2
}
总结
都说是比较难的题目。一开始做的时候确实是一点思路都没有。对付子串（子数组）的方法有
- dp
- 双指针（类似滑动窗口）
- 分治（该题就是采用分治的思路）
这里使用分治，也适用了双指针，类似窗口，首先圈定一个范围，在该范围内字符都是总字符数大于K的，然后再递归计算该子串中最长T长度。不断往后移动窗口，直到遍历完成。
go中map的清空并不提供函数，直接使用make重新申明空间，之前那部分让GC求回收，听说这样还比用情况函数高效。
