至少有 K 个重复字符的最长子串

题目链接

至少有 K 个重复字符的最长子串

题目描述

注意点

• s 仅由小写英文字母组成
• 如果不存在这样的子字符串，则返回 0

解答思路

• 可以使用递归解决本题，需要明确的一点是：如果字符串中有一个字符的出现次数少于k，那么该字符串一定不满足题意，且包含该字符的所有子串都不满足题意。递归有以下步骤：
  • 统计字符串中出现的字符及每个字符的出现次数
  • 如果字符出现次数都不少于k，说明该字符串满足题意，直接返回该字符串的长度
  • 如果有字符出现次数少于k，则根据该字符对字符串进行划分，并将划分后的子串再进行上述操作

代码

class Solution {
    public int longestSubstring(String s, int k) {
        if (k == 1) {
            return s.length();
        }
        if (s.length() < k) {
            return 0;
        }
        // 存储出现的字符及每个字符的出现次数
        int[] charArr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            charArr[idx]++;
        }
        for (int i = 0; i < 26; i++) {
            if (charArr[i] == 0 || charArr[i] >= k) {
                continue;
            }
            char c = (char) (i + 97);
            int res = 0;
            for (String sub : s.split(String.valueOf(c))) {
                res = Math.max(longestSubstring(sub, k), res);
            }
            return res;
        }
        return s.length();
    }
}

关键点

• 找到递归体和递归终止条件
• 如果在某次递归中有多个出现次数少于k次的子串，只需要根据其中任意一个字符划分字符串后形成的子串进行递归即可