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: 

1
2
3
4
5
6
7
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2: 

1
2
3
4
5
6
7
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的字符，作为我们这道题目的分割点。这个字符不符合题意，不会出现在结果里，是可以排除在外的。这样左边的字符串和右边的字符串又可以作为下一层递归的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() > 0){
            int global_stats[26] = {0};
            for(int i = 0; i < s.size(); i++){
                global_stats[s[i] - 'a']++;
            }
            int index = 0;
            int length = 0;
            int tmp_stats[26] = {0};
            for(int i = 0; i < s.size(); i++){
                if(global_stats[s[i] - 'a'] < k){
                    for(int j = 0; j < 26; j++){
                        if(tmp_stats[j] < k){
                            length = 0;
                            break;
                        }
                    }
                    index = i;
                    break;
                }
                else{
                    tmp_stats[s[i] - 'a']++;
                    length++;
                }
            }
            int len1 = longestSubstring(s.substr(0,index), k);
            int len2 = longestSubstring(s.substr(index+1,s.size()), k);
            int maximum = max(len1, len2);
            return max(maximum, length);
        }
        else{
            return 0;
        }
    }
};