Readme

395.Longest-Substring-with-At-Least-K-Repeating-Characters

此题其实并不容易。首先常规的双指针并不适用，假设我们固定左指针是第一个元素，那么右指针最远能移动到哪里呢？我们无法确定。其次，也无法用二分搜值的方法，因为并不是越长的substring就越容易满足条件，反而可能会因为更容易掺入“杂质”而无法满足条件。

解法1：递归

如果把整个序列遍历完，那么我们就得到了所有字符和它出现的频次。对于那些出现次数少于k的字符，是“害群之马”，它们放在任何一个子序列中都会违反题意的。所以一个直观的想法是，将那些“害群之马”作为splitor，将原序列分割成若干子序列，然后递归调用函数本身，找到最长的有效子序列。递归的边界是，如果整个序列所有的字符频次都大于等于k，就可以返回序列的长度；如果整个序列的总长度都小于k，那么就返回零。

注意，这种写法的时间复杂度其实是o(N^2)。虽然有o(N)的分治（递归）写法，但是不是很容易想到，这里省略。

解法2：双指针

本题其实确实有双指针的方法，但是比较特殊。那就是这个滑窗需要固定“不同字母的个数”，这个数目m可以从1遍历到26。只要固定了左指针和区间不同字母的个数，那么我们就可以确定右指针最远的位置，然后查看区间内是否每个字母出现的频次都大于k。可以想见，左指针的移动，必然也会导致右指针的单向移动。

最后的答案就是遍历所有m时能够得到的最大滑窗长度。这种算法的时间复杂度是o(26N).

Leetcode Link