395. Longest Substring with At Least K Repeating Characters

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Code

class Solution {
    public int longestSubstring(String s, int k) {
        return helper(s.toCharArray(), 0, s.length(), k);
    }

    private int helper(char[] str, int start, int end, int k){
        // 停止条件是字符串的长度小于k
        if(end - start < k) {
            return 0;
        }

        int[] count = new int[26];

        // 统计字符串
        for(int i = start; i < end; i++){
            int idx = str[i] - 'a';
            count[idx]++;
        }

        // 这样遍历字母的原因是只要遍历到不满足条件的字符就会找到答案
        // 答案一定在左边或者右边
        for(int i = 0; i < 26; i++){
            // 下面这个是不满足要求的字符, 它不能出现在任何有效的子字符串中
            if(count[i] < k && count[i] > 0){
                // 需要找到这个字符的位置, 然后分别求解它的左半部分和右半部分
                for(int j = start; j < end; j++){
                    if(str[j] == i + 'a'){
                        int left = helper(str, start, j, k);
                        int right = helper(str, j + 1, end, k);
                        return Math.max(left, right);
                    }
                }
            }
        }

        // 用于返回有效的子字符串, 即每个字符都是满足条件的，
        // 没有在for循环return
        return end - start;
    }
}