【C语言刷LeetCode】395. 至少有 K 个重复字符的最长子串(M)

【

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
 

提示：

1 <= s.length <= 104
s 仅由小写英文字母组成
1 <= k <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

】

这道题有些意思，需要用到分治法：

计算所有字符的出现次数cnt[26];
根据1<=cnt[i] 根据ch将字符串拆分, 递归处理拆分后的字符串;
递归终止条件, 字符串中没有满足1<=cnt[i]

int retmax;
 
void Dfs(char *s, int l, int r, int k)
{
    int i;
    int cnt[26] = {0};
 
    for (i = l; i <= r; i++) {
        cnt[s[i] - 'a']++;
    }
 
    char sqilt = 0;
    for (i = l; i <= r; i++) {
        if (cnt[s[i] - 'a'] < k && cnt[s[i] - 'a'] != 0) { // 这个字符出现次数小于k
            sqilt = s[i];
            break;
        }
    }
 
    if (sqilt == 0) { // 每一个字符出现次数都不少于k
        retmax = fmax(retmax, r - l + 1);
        return;
    }
 
    while (l <= r) {
        while (l <= r && s[l] == sqilt)  { // 找第一个不等于sqilt的位置
            l++;
        }
 
        if (l > r) {  // 这段字符里都是 sqilt，不可能有符合的字符串了
            return;
        }
 
        int start = l; // 记录这个位置
 
        while(l <= r && s[l] != sqilt) { // 找到第一个等于sqilt的位置
            l++;
        } // 这次while循环完，不用判断 l > r,因为最终都是要l-1
 
        Dfs(s, start, l - 1, k);
        l++;
    }
}
 
int longestSubstring(char * s, int k){
    int len = strlen(s);
    retmax = 0;
 
    Dfs(s, 0, len - 1, k);
 
    return retmax;
}