当前位置：首页 > article >正文

力扣 395. 至少有 K 个重复字符的最长子串递归

article 2025/2/22 20:16:20

Problem: 395. 至少有 K 个重复字符的最长子串

🍻 递归

🧑‍🏫 参考题解
在这里插入图片描述

⏰ 时间复杂度： $O (n * 26 * 26)$
🌍 空间复杂度： $O (26 * 26)$

class Solution {
    // 想象成一个黑盒函数
    // 输入：字符串 s，要求字符串中的每个字符至少出现 k 次
    // 输出：满足题目规则的最长字符串的长度
    public int longestSubstring(String s, int k) {
        if (s.length() < k) return 0; // 递归出口：不可能出现合法情况则结束
        HashMap<Character, Integer> counter = new HashMap();
        // 字符计数
        for (int i = 0; i < s.length(); i++) {
            counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);
        }
        // 判断是否符合满足：至少每个字符出现 k 次的条件
        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();
    }
}

查看全文

http://www.kler.cn/a/548028.html