395. 至少有K个重复字符的最长子串
image.png
分治算法实现
- 如果一个字符在s中出现的次数小于k次,那么我们就可以把这个字符进行分割为2部分分别统计长度
- 如果s中所有字符出现的次数均大于k次，那么最大的长度就为s的长度
优化
- 如果s的长度小于k，则一定不满足
- 防止每次需要遍历s计算每个字符的数量，可以讲之前统计的字符数量作为参数传进来
细节见注释
/**
分治算法实现
1. 如果一个字符在s中出现的次数小于k次,那么我们就可以把这个字符进行分割为2部分分别统计长度
2. 如果s中所有字符出现的次数均大于k次，那么最大的长度就为s的长度
优化
1. 如果s的长度小于k，则一定不满足
2. 防止每次需要遍历s计算每个字符的数量，可以讲之前统计的字符数量作为参数传进来
*/
func longestSubstring(s string, k int) int {
// 预计算每个字符的数量
A := make([]int,26)
for i:=range s{
c := s[i]-'a'
A[c]++
}
return getCnt(s,k,A)
}
func getCnt(s string,k int,A []int)int{
if len(s)<k{ // 如果s的长度小于k，则一定不满足, 返回0
return 0
}
// 辅助数组B 统计字符串前半部分的 每个字符长度
B := make([]int,26)
for i := range s{
c := s[i]-'a'
if A[c]<k{
for j:=range A{
A[j]-=B[j]
// A[c]-- // 这边可计算，可不计算，因为 本身已经不满足了，-1的必要性不大
}
return max(getCnt(s[:i],k,B),getCnt(s[i+1:],k,A))
}
B[c]++
}
return len(s)
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
