友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
395. Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.Example 1:
Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.解题思路：递归拆分子串，分治。先统计出每个字符出现的频次，维护一对双指针，从首尾开始统计，从首尾往中间排除，如果出现次数小于k则不可能出现在最终子串中，排除并挪动指针，然后得到临时子串，依次从头遍历，一旦发现出现频次小于k的字符，以该字符为分割线，分别递归求其最大值返回。
参考资料
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.Example 2:
Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Longest Substring with At Least K Repeating Characters.
*
* Memory Usage: 38.7 MB, less than 10.00% of Java online submissions for Longest Substring with At Least K Repeating Characters.
*
* Copy from: https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/javadi-gui-by-tzfun/[Java递归 - 至少有K个重复字符的最长子串 - 力扣（LeetCode）]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-27 16:28
*/
public int longestSubstring(String s, int k) {
if (Objects.isNull(s) || s.length() == 0 || k > s.length()) {
return 0;
}
if (k < 2) {
return s.length();
}
return count(s.toCharArray(), k, 0, s.length() - 1);
}
private int count(char[] chars, int k, int start, int end) {
if (end - start + 1 < k) {
return 0;
}
int[] times = new int[26];
for (int i = start; i <= end; i++) {
++times[chars[i] - 'a'];
}
while (end - start + 1 > k && times[chars[start] - 'a'] < k) {
++start;
}
while (end - start + 1 > k && times[chars[end] - 'a'] < k) {
--end;
}
if (end - start + 1 < k) {
return 0;
}
for (int i = start; i <= end; i++) {
if (times[chars[i] - 'a'] < k) {
return Math.max(count(chars, k, start, i - 1), count(chars, k, i + 1, end));
}
}
return end - start + 1;
}