Longest Substring with At Least K Repeating Characters

题目地址：
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/#/description

题目：

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.

解题思路：
这道题主要是用divide and conquer的思想，每当遇到少于k的char就需要divide。然后可以做一点点优化。

代码：

public int longestSubstring(String s, int k) {
    return dc(s, 0, s.length(), k);
}

public int dc(String s, int start, int end, int k) {
    if (end - start < k) return 0;
    int[] cnt = new int[26];
    for (int i = start; i < end; i++) {
        cnt[s.charAt(i) - 'a']++;
    }
    for (int i = start; i < end; i++) {
        if (cnt[s.charAt(i) - 'a'] < k) {
            int left = (i - start < k) ? Integer.MIN_VALUE : dc(s, start, i, k);
            int right = (end - i - 1 < k) ? Integer.MIN_VALUE : dc(s, i + 1, end, k);
            return (left == Integer.MIN_VALUE && right == Integer.MIN_VALUE) ? 0 : Math.max(left, right);
        }
    }
    return end - start;
}