395 Longest Substring with At Least K Repeating Characters

1. Question

Find the length of the longest substringTof a given string (consists of lowercase letters only) such that every character inTappears no less thanktimes.
Example 1:
1
Input: s = "aaabb", k = 3
2
3
Output: 3
4
5
The longest substring is "aaa", as 'a' is repeated 3 times.
Copied!
Example 2:
1
Input: s = "ababbc", k = 2
2
3
Output: 5
4
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Copied!

2. Implementation

(1) Two Pointers + Hash
思路: 由于题目说了string只包含lowercase的字母,所以我们可以列举包含1个字母到包含全部26个字母情况下,找出满足条件的最长子串.其中unique代表不同的字母个数,atLeastK代表在子串中重复出现的次数至少k次的字母的个数
1
class Solution {
2
public int longestSubstring(String s, int k) {
3
int[] map = new int[256];
4
int start = 0, end = 0, unique = 0, atLeastK = 0;
5
int maxLen = 0;
6
7
for (int target = 1; target <= 26; target++) {
8
Arrays.fill(map, 0);
9
start = 0;
10
end = 0;
11
unique = 0;
12
atLeastK = 0;
13
14
while (end < s.length()) {
15
if (map[s.charAt(end)] == 0) {
16
++unique;
17
}
18
19
if (map[s.charAt(end)] == k - 1) {
20
++atLeastK;
21
}
22
23
++map[s.charAt(end)];
24
++end;
25
26
while (unique > target) {
27
if (map[s.charAt(start)] == k) {
28
--atLeastK;
29
}
30
31
if (map[s.charAt(start)] == 1) {
32
--unique;
33
}
34
--map[s.charAt(start)];
35
++start;
36
}
37
38
// 当子串中不同字母的个数等于target,且所以这些不同的字母至少出现k次,更新maxLen
39
if (unique == target && atLeastK == unique) {
40
maxLen = Math.max(maxLen, end - start);
41
}
42
}
43
}
44
return maxLen;
45
}
46
}
Copied!
(2) Divide and Conquer
1
class Solution {
2
public int longestSubstring(String s, int k) {
3
return findLongestSubstring(s, k, 0, s.length() - 1);
4
}
5
6
public int findLongestSubstring(String s, int k, int start, int end) {
7
if (start > end || end - start + 1 < k) {
8
return 0;
9
}
10
11
int[] count = new int[26];
12
for (int i = start; i <= end; i++) {
13
++count[s.charAt(i) - 'a'];
14
}
15
16
for (int i = 0; i < 26; i++) {
17
if (count[i] > 0 && count[i] < k) {
18
int index = s.indexOf((char)(i + 'a'), start);
19
20
return Math.max(findLongestSubstring(s, k, start, index - 1), findLongestSubstring(s, k, index + 1, end));
21
}
22
}
23
return end - start + 1;
24
}
25
}
Copied!

3. Time & Space Complexity

Two Pointers + Hash: 时间复杂度O(26 * n), 空间复杂度O(1)
Divide and Conquer: 时间复杂度O(n^2), 空间复杂度O(n)