395. 至少有 K 个重复字符的最长子串

395. 至少有 K 个重复字符的最长子串

class Solution {
public:
    int dfs(string &s, int l, int r, int k) {
        int cnt[300];
        memset(cnt, 0, sizeof cnt);
        for (int i = l; i <= r; i++)cnt[s[i]]++;
        char split = 0;
        for (int i = 'a'; i <= 'z'; i++)
            if (cnt[i] > 0 && cnt[i] < k) {
                split = i;
                break;
            }

        if (split == 0)return r - l + 1;

        int i = l, res = 0;
        while (i <= r) {
            while (i <= r && s[i] == split)i++;
            if (i > r) break;
            int start = i;
            while (i <= r && s[i] != split)i++;
            int cur = dfs(s, start, i - 1, k);
            res = max(res, cur);
        }
        return res;
    }

    int longestSubstring(string s, int k) {
        return dfs(s, 0, s.size() - 1, k);
    }
};