395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

解题要点：

先设立一个长度为26的数组，用来存储原始字符串的出现次数。遍历原字符串并检测是否有不符合条件的字符，如果没有，加进最终长度。接下来由检测到的第一个不符合要求的字符来分开字符串，并递归。用此方法可将所有满足条件的substring长度都做一次比较，最后返回最大值。

class Solution {
    int res = 0;  
    public int longestSubstring(String s, int k) {
        longest(s, k);
        return res;
    }
    
    public void longest(String s, int k){
        if(s.length() < k) return;
        int[] count = new int[26];
        for(char c : s.toCharArray()) count[c - 'a']++;
        
        boolean valid = true;
        char temp = 'a';
        for(int i = 0; i < s.length(); i++){
            if(count[s.charAt(i) - 'a'] < k){
                valid = false;
                temp = s.charAt(i);
            }
        }
        if(valid){
            res = Math.max(s.length(), res);
            return;
        }
        String[] sub = s.split(Character.toString(temp), 2);
        for(String ss: sub)
            longest(ss, k);        
    }
}