Longest Substring with At Least K Repeating Characters 395

Question

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.

Solution

这个不是一般的DP或者暴力的解决方式，要用一下递归：

1. 统计每个字母【只有小写】出现的次数

2. 找出不合法的字符【出现了，但是次数不够K】

3. 如果没有任何不合法字符，那么返回串的长度 （别忘了）

4. 如果有不合法的字符，那么将这个串按照本轮不合法的字符位置切开（一个不合法的字符就切一刀），切开后的每一个子串递归执行1，取最长的返回

5. 记得算上最后一段（即切结尾的那一刀）

代码如下：

public class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() < k) {
            return 0;
        }

        if (k <= 1) {
            return s.length();
        }

        char[] ss = s.toCharArray();
        int[] counter = new int[26];
        boolean[] valid = new boolean[26];
        //统计每个字符的长度
        for (int i = 0; i < s.length(); i++) {
            counter[ss[i] - 'a']++;
        }
        //检查当前字符串是否是完全满足的
        boolean isValid = true;
        //判断每个字符的出现条件是否合适，即，要么不出现，要么出现了不少于k
        for (int i = 0; i < 26; i++) {
            if (counter[i] > 0 && counter[i] < k) {
                valid[i] = false;
                isValid = false;
            } else {
                valid[i] = true;
            }
        }

        if (isValid) {
            return s.length();
        }

        int start = 0;
        int longest = 0;
        for (int i = 0; i < ss.length; i++) {
            if (!valid[ss[i] - 'a']) {
                if (start < i) {
                    //把不符合要求的断开，然后依次检查 取最大
                    String str = s.substring(start, i);
                    longest = Math.max(longest, longestSubstring(str, k));
                }
                start = i + 1;
            }
        }
        //记得算上最后一段（比如从某个start开始到结尾一直都是valid，这样在上面的for循环中就不能取到最后一段）
        longest = Math.max(longest, longestSubstring(s.substring(start, s.length()), k));

        return longest;
    }
}