分治

至少有K个重复字符的最长子串(https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/)

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:
输入:
s = "aaabb", k = 3
输出:
3
最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:
输入:
s = "ababbc", k = 2
输出:
5
最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

分治
先用hash表统计s中每个字符出现的次数，显然如果字符c出现的次数小于k，c必然不在最长子串里面，根据这个特性可以将原始s分割成多个子串递归地求解问题，我们用一个split数组依次来存放每个分割点的索引，对每个分割区间同样求解该问题(多路的分治问题)，并取结果的最大值保存在变量ans中，此处有一个小trick（如果当前求解的子串长度比已存在的ans还要小，则没有必要求解该区间，这样可以减少不必要的计算），最后递归的结束点就是当前求解的字符串s符合最长子串的要求。

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

        Map<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            countMap.put(s.charAt(i), countMap.getOrDefault(s.charAt(i), 0) + 1);
        }

        List<Integer> splitter = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (countMap.get(s.charAt(i)) < k) {
                splitter.add(i);
            }
        }

        int ans = 0;
        int left = 0;

        if (splitter.size() == 0) {
            ans = s.length();
            return ans;
        }

        for (int i = 0; i < splitter.size(); i++) {
            int right = splitter.get(i);
            if (right - left > ans) {
                ans = Math.max(ans, longestSubstring(s.substring(left, right), k));
            }
            left = right + 1;
        }
        if(left < s.length() && (s.length()-left) > ans){
            ans = Math.max(ans, longestSubstring(s.substring(left), k));
        }

        return ans;