LeetCode(395) -- Longest Substring with At Least K Repeating Characters

Problem

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

输入:
s = "aaabb", k = 3

输出:
3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。

Solution

class Solution {
    public int longestSubstring(String s, int k) {
        char[] str = s.toCharArray();
        int[] countMap = new int[26];
        int maxUnique = getMaxUniqueLetters(s);
        int result = 0;
        for (int currUnique = 1; currUnique <= maxUnique; currUnique++) {
            Arrays.fill(countMap, 0);
            int windowStart = 0, windowEnd = 0, idx = 0, unique = 0, countAtLeastK = 0;
            while (windowEnd < str.length) {
                if (unique <= currUnique) {
                    idx = str[windowEnd] - 'a';
                    if (countMap[idx] == 0) unique++;
                    countMap[idx]++;
                    if (countMap[idx] == k) countAtLeastK++;
                    windowEnd++;
                } else {
                    idx = str[windowStart] - 'a';
                    if (countMap[idx] == k) countAtLeastK--;
                    countMap[idx]--;
                    if (countMap[idx] == 0) unique--;
                    windowStart++;
                }
                if (unique == currUnique && unique == countAtLeastK)
                    result = Math.max(windowEnd - windowStart, result);
            }
        }
        return result;
    }
    
    int getMaxUniqueLetters(String s) {
        boolean map[] = new boolean[26];
        int maxUnique = 0;
        for (int i = 0; i < s.length(); i++) {
            if (!map[s.charAt(i) - 'a']) {
                maxUnique++;
                map[s.charAt(i) - 'a'] = true;
            }
        }
        return maxUnique;
    }
}

sliding window， 44%

The Best Solution

class Solution {
    public int longestSubstring(String s, int k) {
        return dfs(s, k,  0, s.length());
    }
    private int dfs(String s, int k, int begin, int end){
        int[] charNums = new int[26];
        for (int i = begin; i < end; i++){
            int idx = s.charAt(i) - 'a';
            charNums[idx]++;
        }
        int res = 0;
        int new_begin = begin;
        for (int i = begin; i < end; i++){
            int idx = s.charAt(i) - 'a';
            if (charNums[idx] > 0 && charNums[idx] < k) {
                if (i - new_begin >= k) res = Math.max(res, dfs(s, k, new_begin, i));
                new_begin = i+1;
            }
        }
        if (new_begin == begin) return end - begin;
        return Math.max(res, dfs(s, k, new_begin, end));
    }
}