至少有 K 个重复字符的最长子串-DFS

1、题目描述

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

2、解题思路

（1）分治思想 对于每一层 找到第一个坏的字符 然后进行分割 将分割后的字符串进行递归 满足情况则按照栈的结构返回答案 （递归深度大）

（2）分治思想 对于每一层 找到所有坏的字符 然后进行分割 将分割后的字符串进行递归 满足情况则按照栈的结构返回答案 （递归深度小）

针对思路一，先用strtok函数进行分割，超时（19 / 38）后，改为手动分割，但仍然超时（33 / 38 ）。

针对思路二：通过 38 / 38 个通过的测试用例。

3、算法

（1）思路一，strtok函数进行分割

#include <string.h>
#define MAX(a, b) (a > b ? a : b)

int longestSubstring(char* s, int k) {
    // 1、存储所有字符出现的次数
    int flag[26] = {0};
    int n = strlen(s);
    // 快速剪枝
    if (n < k) return 0;
    for (int i = 0; i < n; i++) {
        flag[s[i] - 'a']++;
    }
    // 2、查找第一个坏的字符（因为不断递归 能遍历到所有情况 所以查找第一个坏的字符即可）
    for (int i = 0; i < n; i++) {
        if (flag[s[i] - 'a'] < k && flag[s[i] - 'a'] > 0) {
            // 3、递归并更新答案
            char split_c = s[i];
            int c_max_len = 0;
            char t_s[n + 1]; //（包括\0）
            strcpy(t_s, s); //（避免修改s）
            char* c_s = strtok(t_s, (char[]){split_c, '\0'}); // （分割的第一段）
            while (c_s != NULL) {
                c_max_len = MAX(c_max_len, longestSubstring(c_s, k));
                c_s = strtok(NULL, (char[]){split_c, '\0'}); // （分割的后面几段）
            }
            return c_max_len;
        }
    }
    return n;
}

时间复杂度分析：

理论复杂度：O(26 * N) 26是最大的递归深度

额外：A. 频繁的 strlen：O(N) B. 数组内存分配与拷贝：O(N) C. strtok 的副作用

（2）思路一，手动进行分割

#include <string.h>
#define MAX(a, b) (a > b ? a : b)


int helper(char* s, int start, int end, int k) {
    if (end - start + 1 < k) return 0;
    // 1. 统计当前区间内字符频次
    int flag[26] = {0};
    for (int i = start; i <= end; i++) {
        flag[s[i] - 'a']++;
    }
    // 2. 寻找第一个坏字符
    for (int i = start; i <= end; i++) {
        if (flag[s[i] - 'a'] > 0 && flag[s[i] - 'a'] < k) {
            int max_len = 0;
            int next_start = start;
            // 3. 原地切分：跳过坏字符，递归处理每一段
            for (int j = start; j <= end; j++) {
                if (s[j] == s[i]) { // 发现分割点
                    max_len = MAX(max_len, helper(s, next_start, j - 1, k));
                    next_start = j + 1;
                }
            }
            // 不要忘记处理最后一段
            max_len = MAX(max_len, helper(s, next_start, end, k));
            return max_len;
        }
    }
    // 如果没有坏字符，整个区间都合格
    return end - start + 1;
}
int longestSubstring(char* s, int k) {
    return helper(s, 0, strlen(s) - 1, k);
}

时间复杂度分析：

理论复杂度：O(26 * N) 26是最大的递归深度

手动分割用到索引，产生的额外时间复杂度很少，但是仍然每次只找第一个切分点，递归深度仍然较大。

（3）思路二

#include <string.h>
#define MAX(a, b) (a > b ? a : b)

int helper(char* s, int start, int end, int k) {
    // 剪枝
    if (end - start + 1 < k) return 0;

    int flag[26] = {0};
    for (int i = start; i <= end; i++) {
        flag[s[i] - 'a']++;
    }

    // 递归出口
    int i = start;
    while (i <= end && flag[s[i] - 'a'] >= k) {
        i++;
    }
    if (i > end) return end - start + 1;

    // 以区间内所有“坏字符”为界，拆分出多个子段
    int max_len = 0;
    int curr_start = start;
    while (curr_start <= end) {
        // 1. 找s[start:end+1]中该子段的起点
        while (curr_start <= end && flag[s[curr_start] - 'a'] < k) {
            curr_start++;
        }
        if (curr_start > end) break;
        
        // 2. 找s[start:end+1]中该子段的终点
        int curr_end = curr_start;
        while (curr_end <= end && flag[s[curr_end] - 'a'] >= k) {
            curr_end++;
        }
        
        // 3. 递归这一段
        max_len = MAX(max_len, helper(s, curr_start, curr_end - 1, k));
        // 4.设置s[start:end+1]中下一字段可能的起点
        curr_start = curr_end;
    }

    return max_len;
}

int longestSubstring(char* s, int k) {
    return helper(s, 0, strlen(s) - 1, k);
}

时间复杂度分析：

理论复杂度：O(26 * N) 26是最大的递归深度 但基本不会到达26 通常只有2-5层 因为在每一层分割了所有不满足情况字符