LeetCode 395 至少有 K 个重复字符的最长子串 - 分治解法
🟠 中等偏上 https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
思路
这题思路不太直观，可以用滑动窗口，也可以用分治。
分治关键在于“如何切分”：
- 若某字符在当前字符串中的出现次数小于
k，它不可能出现在合法答案中。 - 因此可以把这些字符当作分隔符，把原串切成多个子串，分别递归求解，再取最大值。
class Solution {
public:
int longestSubstring(string s, int k) {
unordered_map<char,int> hash_map;
for(auto c:s) hash_map[c]++;
vector<int> split_index;
for(int i = 0;i<s.size();i++){
if(hash_map[s[i]]<k){
split_index.push_back(i);
}
}
if(split_index.size()==0) return s.size();
int ans = 0;
int left = 0;
split_index.push_back(s.size());
for(int i = 0;i<split_index.size();i++){
int len = split_index[i]-left;
if(len>ans) ans = max(ans,longestSubstring(s.substr(left,len),k));
left = split_index[i]+1;
}
return ans;
}
};