class Solution {
    public int longestSubstring(String s, int k) {
        int len = s.length();
        return dfs(s, 0, len-1, k);
    }

    public int dfs(String s, int l, int r, int k) {
        //先统计字符串s中，每个字母出现的次数，一共有26个小写字母
        int[] num = new int[26];
        for (int i = l; i <= r; i++) {
            num[s.charAt(i) - ‘a‘]++;
        }

        // 然后找到字符串s中第一个不满足题意的字符
        char splite = 0;
        for (int i = 0; i < 26; i++) {
            if (num[i] > 0 && num[i] < k) {
                splite = (char) (i+‘a‘);
                break;
            }
        }

        // 如果没找到不满足题意的字符，说明字符串s符合题意，直接返回字符串s的本身（最长）长度
        if (splite == 0) {
            return r-l+1;
        }

        // 如果找到了字符splite，就要以splite为界划分子串
        int i = l;
        int res = 0;
        while (i<=r) {
            // 先找到第一个不等于splite的字符下标
            while (i<=r && s.charAt(i) == splite) {
                i++;
            }

            if (i > r) {
                break;
            }
            int start = i;  // 保存一下结果
            // 再找最后一个不等于splite的下标
            while(i<=r && s.charAt(i) != splite) {
                i++;
            }
            
            // 分治
            int len = dfs(s, start, i-1, k);
            res = Math.max(res, len);
        }

        return res;
    }
}