LeetCode: Longest Substring with At Least K Repeating Characters

LeetCode: 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:

1
2
3
4
5
6
7
Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

1
2
3
4
5
6
7
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution

Split the input string with the characters whose count is smaller than k, then try to find the results in each chunk

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
class Solution {
public int longestSubstring(String s, int k) {
if (s == null || s.isEmpty() || k > s.length()) return 0;

Map<Character, Integer> dict = new HashMap<>();

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
dict.put(c, dict.getOrDefault(c, 0) + 1);
}

Set<Character> set = new HashSet<>();
for (Map.Entry<Character, Integer> entry : dict.entrySet()) {
if (entry.getValue() < k) {
set.add(entry.getKey());
}
}

if (set.isEmpty()) return s.length();

int result = 0;
int pre = 0;
for (int i = 0; i < s.length() ; i++) {
char c = s.charAt(i);
if (set.contains(c)) {
result = Math.max(result, longestSubstring(s.substring(pre, i), k));
pre = i + 1;
}

}
result = Math.max(result, longestSubstring(s.substring(pre, s.length()), k));
return result;
}
}