05 August 2008
至少有k个重复字符的最长字串（每个字符都不少于k次）- 递归+hashmap
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) {
Map<Character, Integer> map = new HashMap<>();
// 1. 统计字符串中各个字符的词频
for (int i = 0;i < s.length();i++) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)+1);
}
// 2. 使用一个list 来记录分割点，当出现词频小于k的字符时，分割字符串
List<Integer> split_index = new ArrayList<>();
for (int i = 0;i < s.length();i++) {
if (map.get(s.charAt(i)) < k)
split_index.add(i);
}
// 3. 如果没有分割点，说明字符串是符合条件的，返回长度
if (split_index.size() == 0) return s.length();
// 4. 遍历分割点,递归处理每个子串（子串被分割后，内部的词频可能不符合条件了）
int left = 0, ans = 0;
// 注意把最后一个位置放进来，这样才能处理到最后一个子串(例如 bbaaa)
split_index.add(s.length());
for (int i = 0;i < split_index.size();i++) {
// 分割点的左侧 符合条件的子串长度
int lenOfSubstring = split_index.get(i) - left;
// 递归处理子串
ans = Math.max(ans, longestSubstring(s.substring(left, left+lenOfSubstring), k));
// 更新起始位置
left = split_index.get(i) + 1;
}
return ans;
}
}