content: package question0395_longest_substring_with_at_least_k_repeating_characters;
  
  /**
   * 分治算法。
   *
   * 时间复杂度是O(nlogn)，其中n是字符串s的长度。空间复杂度是O(logn)。
   * 
   * 执行用时：1ms，击败75.54%。消耗内存：40.7MB，击败5.07%。
   */
  public class Solution {
  
    public int longestSubstring(String s, int k) {
      int n;
      if (null == s || (n = s.length()) == 0 || k > n) {
        return 0;
      }
      if (k == 1) {
        return n;
      }
      return longestSubstring(s, k, 0, n - 1);
    }
  
    private int longestSubstring(String s, int k, int left, int right) {
      if (right - left + 1 < k) {
        return 0;
      }
      int[] count = new int[26];
      for (int i = left; i <= right; i++) {
        count[s.charAt(i) - 'a']++;
      }
      while (right - left + 1 > k && count[s.charAt(left) - 'a'] < k) {
        left++;
      }
      while (right - left + 1 > k && count[s.charAt(right) - 'a'] < k) {
        right--;
      }
      for (int i = left; i < right; i++) {
        if (count[s.charAt(i) - 'a'] < k) {
          return Math.max(longestSubstring(s, k, left, i - 1), longestSubstring(s, k, i + 1, right));
        }
      }
      return right - left + 1;
    }
  
  }