LeetCode395 至少有K个重复字符的最长子串 golan

395. 至少有K个重复字符的最长子串

分治算法实现

1. 如果一个字符在s中出现的次数小于k次,那么我们就可以把这个字符进行分割为2部分分别统计长度
2. 如果s中所有字符出现的次数均大于k次，那么最大的长度就为s的长度

优化

1. 如果s的长度小于k，则一定不满足
2. 防止每次需要遍历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
}