给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
示例1：
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例2：
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
提示：
1 <= s.length <= 104
s 仅由小写英文字母组成
1 <= k <= 105
Java解法
思路：
- 子串当中包含所有 字母个数必须大于k
- 设想1：
- 过滤出不满足个数的子母
滑动窗口进行遍历
遇到不满足个数字母时自检，移除个数不满足长度的部分记录最大值，直到遍历完成- 参考分治思想：实际已经想到了，但是没有完全分治下去
package sj.shimmer.algorithm.m4_2021;
import java.util.HashMap;
import java.util.Map;
/**
* Created by SJ on 2021/4/28.
*/
class D91 {
public static void main(String[] args) {
// System.out.println(longestSubstring("aaabb", 3));
// System.out.println(longestSubstring("ababb", 3));
System.out.println(longestSubstring("ababb", 2));
}
public static int longestSubstring(String s, int k) {
if (s == null || s.length() < k) {
return 0;
}
int len = s.length();
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
Integer num = map.getOrDefault(s.charAt(i), 0);
map.put(s.charAt(i), ++num);
}
Character split = null;
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue()<k) {
split = entry.getKey();
break;
}
}
if (split!=null) {
String[] splits = s.split(String.valueOf(split));
int num = 0;
for (String s1 : splits) {
num = Math.max(num, longestSubstring(s1, k));
}
return num;
} else {
return len;
}
}
}
image
官方解
- 分治：思路一致
- 滑动窗口：和我设想差不多，校验内部时带来了很多的复杂记录
