LeetCode 395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

解析：给定一个字符串和一个数值k，返回子串中字符出现次数不少于K的最大长度。比如示例中的s=”ababbc”,k=2，则满足条件的最大子串为”ababb”，子串中每个字符出现的次数都不少于k。

思路：采用递归的方式处理，首先遍历字符，然后记录每个字符出现的次数。从头开始判断每个字符出现次数是否超过k，如果当前字符低于K则不能出现在结果中，当前字符将整个字符串s分为了两部分，分别递归的处理左右部分，然后选择长度最大的一个即可。代码如下：

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() == 0 || k > s.size())
            return 0;
        if(k == 0)
            return s.size();
        unordered_map<char, int> count_map;
        for(int i=0; i < s.size(); i++)
        {
            count_map[s[i]] ++;
        }
        int idx = 0;
        while(idx < s.size() && count_map[s[idx]] >= k)
            idx ++;
        if(idx == s.size()) 
            return s.size();
        int left = longestSubstring(s.substr(0, idx), k);
        while (idx < s.size() && count_map[s[idx]] < k) 
            ++idx;
        int right = longestSubstring(s.substr(idx), k);
        return max(left, right);
    }
};

参考：

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87736/C%2B%2B-recursive-solution