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

/*
 * @lc app=leetcode.cn id=395 lang=cpp
 *
 * [395] 至少有 K 个重复字符的最长子串
 */

// @lc code=start
class Solution {
public:

    int dfs(string &s, int &k, int x, int y) {
        if (x > y) return 0;
        int vis_word[26];
        memset(vis_word, 0, sizeof(vis_word));
        for (int i = x; i <= y; i++) {
            vis_word[s[i] - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (vis_word[i] >= k) vis_word[i] = 0;
        }
        int l = x, r = y;
        while(l <= y) {
            if (vis_word[s[l] - 'a']) {
                break;
            }
            l++;
        }
        while(r >= x) {
            if (vis_word[s[r] - 'a']) {
                break;
            }
            r--;
        }
        if (l > r) return y - x + 1;
        int len1 = dfs(s, k, x, l - 1);
        int len2 = dfs(s, k, r + 1, y);
        int len3 = dfs(s, k, l + 1, r - 1);
        return max(max(len1, len2), len3);
    }

    int longestSubstring(string s, int k) {
        return dfs(s, k, 0, s.length() - 1);
    }
};
// @lc code=end