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.

Input:
s = "aaabb", k = 3

Output:
3

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

Thinking:

  • Method: Brutal force
class Solution {
    public int longestSubstring(String s, int k) {
        if(s == null || s.length() < k) return 0;
        int len = s.length();
        char[] arr = s.toCharArray();
        int result = 0;
        for(int i = 0; i < len - k + 1; i++){
            int[] count = new int[26];
            int temp = i;
            loop:
            for(int j = i + k; j <= len; j++){
                for(; temp < j; temp++){
                    count[arr[temp] - 'a']++;
                }
                for(int p = 0; p < 26; p++)
                    if(count[p] > 0 && count[p] < k)
                        continue loop;
                result = Math.max(result, j - i);
            }
        }
        return result;
    }
}
  • Method 2: divide-and-conquer
    • 我们先统计所有字符出现的次数，再找出其中出现次数大于0小于K的，说明出现了但是造成了问题的这些元素。
    • 然后我们通过分治，分别获取其左右的数组继续递归，而最终的结果一定出现在左右的子数组中。
class Solution {
    public int longestSubstring(String s, int k) {
        if(s == null || s.length() == 0) return 0;
        char[] arr = s.toCharArray();
        return helper(arr, 0, arr.length, k);
    }
    private static int helper(char[] arr, int start, int end, int k){
        if(end - start < k) return 0;
        int[] count = new int[26];
        for(int i = start; i < end; i++){
            count[arr[i]-'a']++;
        }
        for(int i = start; i < end; i++){
            if(count[arr[i] - 'a'] > 0 && count[arr[i] - 'a'] < k){
                return Math.max(helper(arr, start, i, k), helper(arr, i + 1, end, k));
            }
        }
        return end - start;
    }
}