Longest Substring with At least K repeating characters

这是分治里面碰到过的最复杂的一道题，首先它迷惑性很强，看到这个标题很容易会让人去往双指针去想，虽然这道题确实双指针也不是不能做，但是逻辑很复杂，这里最自然的想法是首先找到这个字符串里面有哪些字母总出现次数达不到K的要求，如果没有这样的字母，直接返回字符串长度就行了，如果有这样的字母，把他们的位置一个个标记下来，然后利用这些标记在字符中划隔板，每个隔板继续递归上面的步骤，知道子字符串的长度都小于K了就触底反弹，所以这里我们实际上把求一个最长子字符串的问题变成了判断一个字符串是不是所有字母都出现了K次的问题，问题的求解难度变小了，另外时间复杂度不太好想，但是的确是O(n^2)

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        n = len(s)
        if n < k:
            return 0

        tmp = collections.defaultdict(list)
        for index, char in enumerate(s):
            tmp[char].append(index)

        checker = []
        for key, value in tmp.items():
            if len(value) < k:
                checker += value

        if not checker:
            return n

        result = 0
        preIndex = -1
        for index in checker:
            result = max(result, self.longestSubstring(s[preIndex + 1 : index], k))
            preIndex = index

        result = max(result, self.longestSubstring(s[preIndex + 1:len(s)], k))

        return result

    def check(self, string, start, end, count):
        tmp = collections.Counter(string[start + 1:end])
        for value in tmp.values():
            if value < count:
                return False
        return True