[daily training] 395 Longest substring with at least k repeated characters

subject

Give you a string s And an integer k , Please find out s Longest substring in , The number of occurrences of each character in the substring shall not be less than k . Returns the length of this substring .

Example 1：
Input ：s = “aaabb”, k = 3
Output ：3
explain ： The longest string is “aaa” , among ‘a’ repeated 3 Time .

Example 2：
Input ：s = “ababbc”, k = 2
Output ：5
explain ： The longest string is “ababb” , among ‘a’ repeated 2 Time , ‘b’ repeated 3 Time .

Tips ：
1 <= s.length <= 10⁴
s It's only made up of lowercase letters
1 <= k <= 10⁵

Code

package dayLeetCode;

public class dayleetcode395 {
    
    //  Divide and conquer , Pass occurs more than 0 And less than k The character of divides the string into segments 
    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) {
    
        //  Count the number of occurrences of each character 
        int[] cnt = new int[26];
        for (int i = l; i <= r; i++){
    
            cnt[s.charAt(i) - 'a']++;
        }

        //  Statistics less than k The characters of 
        char ch = 0;
        for (int i = 0; i < 26; i++){
    
            if (cnt[i] > 0 && cnt[i] < k){
    
                ch = (char) (i + 'a');
                break;
            }
        }
        //  All greater than 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;
            //  Calculate the position of the rightmost end of the segment 
            while (t <= r && s.charAt(t) != ch){
    
                t++;
            }
            //  Divide and conquer 
            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));
    }
}