写点什么

【LeetCode】至少有 K 个重复字符的最长子串 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 02 月 27 日

题目

找到给定字符串(由小写字符组成)中的最长子串 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<Character, Integer> 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 的子串都不可能满足要求。

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

  • 每日坚持一题,加油!


发布于: 2021 年 02 月 27 日阅读数: 30
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】至少有K个重复字符的最长子串Java题解