找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

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

解题思路

先用hash表统计s中每个字符出现的次数，显然如果字符c出现的次数小于k，c必然不在最长子串里面，根据这个特性可以将原始s分割成多个子串递归地求解问题，我们用一个split数组依次来存放每个分割点的索引，对每个分割区间同样求解该问题(多路的分治问题)，并取结果的最大值保存在变量ans中，此处有一个小trick（如果当前求解的子串长度比已存在的ans还要小，则没有必要求解该区间，这样可以减少不必要的计算），最后递归的结束点就是当前求解的字符串s符合最长子串的要求。

class Solution {
public:
    int longestSubstring(string s, int k)
    {
        //统计各个字符的数量，字符数量小于K的均为分割点
        unordered_map<char, int> charNum;
        for(auto c:s)
        {
            charNum[c]++;
        }
        vector<int> split;
        for (int i = 0; i < s.size(); ++i)
        {
            if (charNum[s[i]] < k)
            {
                split.push_back(i);
            }
        }
        if (split.empty())
            return s.length();
        int ans = 0, left = 0;
        split.push_back(s.length());
        for (int i = 0; i < split.size(); ++i)
        {
            int len = split[i] - left;
            if (len > ans)
                ans = max(ans, longestSubstring(s.substr(left, len),k));
            left = split[i] + 1;
        }
        return ans;
    }

};