题目

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

代码

public class DayCode {
    public static void main(String[] args) {
        String s = "baaabcb";
        int k = 3;
        int ans = new DayCode().longestSubstring(s, k);
        System.out.println("ans is " + ans);
    }

    /**
     * https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring(String s, int k) {
        if (s.length() < k) {
            return 0;
        }
        HashMap counter = new HashMap<>(26);
        for (int i = 0; i < s.length(); i++) {
            counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (char c : counter.keySet()) {
            if (counter.get(c) < k) {
                int res = 0;
                for (String t : s.split(String.valueOf(c))) {
                    res = Math.max(res, longestSubstring(t, k));
                }
                return res;
            }
        }
        return s.length();
    }
}

总结

• 这个题目不长，也容易懂，但是解决起来却不是那么简单。需要思考。

• 题目的核心是，对于字符串 s，如果存在某个字符 char，它的出现次数大于 0 且小于 k，则任何包含 char 的子串都不可能满足要求。

• 根据上述重要信息，就可以求解了。可以用滑动窗口来解决，也可以用递归来解决，相对而言，这里的递归代码更好写。

• 每日坚持一题，加油！