LC395关于分治

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

示例 1:

输入:
s = "aaabb", k = 3

输出:
3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:

输入:
s = "ababbc", k = 2

输出:
5

最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int longestSubstring(string s, int k) {
        //第一步 k的值要过小的话
        if(k<=1)return s.size();
        
        //重要思路 凡是次数小于特定值的字符不应该被包括
        if(s.length()<k)
            return 0;
        //=0;        
        //字符，所以就直接用128位的数组，根本不需要用map
        map<char,int> ex;
        for(int i=0;i<s.length();i++){
           ex[s[i]]+=1;
            // cout<<ex[s[i]]<<endl;
        }
        int i=0;
        while(i<s.length()&&ex[s[i]]>=k){
            i++;
        }
        if(i==s.length()) return s.length();
        int l=longestSubstring(s.substr(0,i),k);
        
        while(i<s.length()&&ex[s[i]]<k){
            i++;
        }
        int r=0;
        if(i<s.length())
            r=longestSubstring(s.substr(i),k);
        
        return max(l,r);

        
        
        
    }
};

以及有一道Python题解，太精妙了

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if not s:
            return 0
        for c in set(s):
            if(s.count(c))<k:
                return max(self.ongestSubstring(t,k) for t in s.split(c))
        return len(s)