Longest Substring with At Least K Repeating Characters

题意

给定一个字符串s,从中寻找最长的子串T，使得T中每种字符出现的次数都不小于k，求出最长的长度。

解法

这种题目完全是短板，参照了别人的代码。其实就是用递归来分治这个字符串。我们知道，T中每种字符出现的次数都不小于k，那么对于任意一个子串，我们找出其中出现次数最少的字符，比如是c，出现了p次，那么如果p是大于k的，说明这整个子串都是符合题目要求的，如果p小于k，那么说明任意包含c的子串是不符合题目要求的，所以我们将c当做是某个子串的分隔符，将子串进行递归的分解，最后求得最长长度。

代码

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if len(s) < k:
            return 0
        c = min(set(s),key=s.count)
        if s.count(c)>=k:
            return len(s)
        return max(self.longestSubstring(t,k) for t in s.split(c))