【日常训练】395. 至少有 K 个重复字符的最长子串

题目

给你一个字符串 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 <= 10⁴
s 仅由小写英文字母组成
1 <= k <= 10⁵

代码

package dayLeetCode;

public class dayleetcode395 {
    
    // 分治，通过出现次数大于0且小于k的字符将字符串划分成若干段
    public int longestSubstring(String s, int k) {
    
        int n = s.length();
       return dfs(s, 0 , n - 1, k);
    }

    private int dfs(String s, int l, int r, int k) {
    
        // 统计每个字符出现次数
        int[] cnt = new int[26];
        for (int i = l; i <= r; i++){
    
            cnt[s.charAt(i) - 'a']++;
        }

        // 统计小于k的字符
        char ch = 0;
        for (int i = 0; i < 26; i++){
    
            if (cnt[i] > 0 && cnt[i] < k){
    
                ch = (char) (i + 'a');
                break;
            }
        }
        // 全部大于k
        if (ch == 0){
    
            return r - l + 1;
        }

        int t = l;
        int ans = 0;
        while (t <= r){
    
            while (t <= r && s.charAt(t) == ch){
    
                t++;
            }
            if (t > r){
    
                break;
            }
            int start = t;
            // 计算该段最右端的位置
            while (t <= r && s.charAt(t) != ch){
    
                t++;
            }
            // 分治
            int len = dfs(s, start, t - 1, k);
            ans = Math.max(ans, len);
        }
        return ans;
    }

    public static void main(String[] args) {
    
        dayleetcode395 obj = new dayleetcode395();
        System.out.println(obj.longestSubstring("aaabb", 3));
    }
}