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

链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/

我们来思考一下什么样的情况可能可以构成连续的子串，每个字符都出现了至少k次；什么情况下又构不成？
很显然如果字符串里有字符在整个串里都没出现k次，那么含有这个字符的子串一定是不可能成立的。那是不是子串里每个字符串都出现了k次就可以呢？ 其实也不是的
举一个例子来说明，如:
s = "abbccddadcbbb" k = 3
其中s[1:6]中的b,c,d都在s中出现了3次以上，那么s[1:6]是否是一个满足条件的子串呢？显然不是因为b,c,d的第k次出现被一个不可能包含在满足条件的子串中的字符a隔开了。而左右两端的每个子串的出现条件就此应该重新计算，而这个计算问题是否和原来的问题一致呢，进而想到了分治的算法。

class Solution {
    public:
    int longestSubstring(string s, int k) {
        if(s.size()==0) return 0;
        return cnt(s, 0, s.size()-1, k);
    }
    int cnt(const std::string& s, int left, int right, int k) {
        std::unordered_map<char, int> count;
        // 统计字符串从left到right的个数
        for(int i = left; i <= right; ++i) {
            count[s[i]]++;
        }
        // 找到字符串中字符>=k的开始
        for(; left <= right; ++left) {
            if(count[s[left]] >= k) {
                break;
            }
        }
        // 找到字符串中字符>=k的结尾
        for(; right >= left; --right) {
            if(count[s[right]] >= k) {
                break;
            }
        }
        // 如果[left, right] < k
        if(right-left+1 < k) {
            return 0;
        }
        int partition = left;
        // 判断[left, right]之间的字符数量是不是都>=k次
        for(; partition <= right; ++partition) {
            if(count[s[partition]] < k) {
                break;
            }
        }
        //  [left, right]之间的字符数量都>=k次
        if(partition >= right) {
            return right-left+1;
        }
        // 分治找到字符串
        return max(cnt(s, left, partition-1, k), cnt(s, partition+1, right, k));
    }
};