Longest Substring with At Least

题目来源
给一个字符串，以及一个数字k，求该字符串子串中每个字符出现的频次都大于等于k。
还是没有想法。
看了下讨论区，就是先遍历一遍，得出各个字符的频次，然后再遍历，找到第一个不符合的。然后分割成前后两块，再进行同样的操作。
能过，不过时间复杂度还是比价高的，平均复杂度应该是O(nlogn)。
代码如下：

class Solution {
public:
    int longestSubstring(string s, int k) {
        int len = s.size();
        int maps[26] = {0};
        for (int i=0; i<len; i++)
            maps[s[i]-'a']++;
        int splitPos = 0;
        while (splitPos < len && maps[s[splitPos] - 'a'] >= k)
            splitPos++;
        if (splitPos == len)
            return len;
        int left = longestSubstring(s.substr(0, splitPos), k);
        int right = longestSubstring(s.substr(splitPos + 1), k);
        return max(left, right);
    }
};

这个复杂度是O(n)，具体的话因为应该是O(26*n)。因为最多递归26次，每次至少去除了一个字母。每层递归的复杂度应该是O(n)。

class Solution {
public:
    int longestSubstring(string s, int k) {
        return longestSubstring_recur(s, k, 0, s.size());
    }
    
    int longestSubstring_recur(const string& s, int k, int start, int end)
    {
        int count[26] = {0};
        for (int i=start; i<end; i++)
            count[s[i] - 'a']++;
            
        int maxLen = 0;
        for (int i=start; i<end; ) {
            while (i < end && count[s[i] - 'a'] < k)
                i++;
            if (i == end)
                break;
            int moreThanK = i;
            while (moreThanK < end && count[s[moreThanK] - 'a'] >= k)
                moreThanK++;
            if (i == start && moreThanK == end)
                return end - start;
            maxLen = max(maxLen, longestSubstring_recur(s, k, i, moreThanK));
            i = moreThanK;
        }
        return maxLen;
    }
};