LeetCode 395 至少有 K 个重复字符的最长子串 - 滑动窗口解法
🟠 中等偏上 https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/
特殊的点
长度没有限制，窗口内的元素有限制：如果用一般的思路：左侧侧何时滑动呢？因为当前窗口内可能不满足条件，如果左边往左扩展可能找到答案，往右也有可能找到答案。因此窗口的滑动规则十分模糊，那如何给窗口一个限制呢？注意到字符集是26个，可以主动限制每次滑动窗口内的字符种类个数。
代码
class Solution {
public:
bool is_ok(unordered_map<char, int> hash_map, int k) {
for (const auto& pair : hash_map) {
if (pair.second < k)
return false;
}
return true;
}
int longestSubstring(string s, int k) {
int res = 0;
//m控制窗口内的种类限制。
for (int m = 1; m <= 26; m++) {
int left = 0;
unordered_map<char, int> hash_map;
for (int i = 0; i < s.size() && m <= 26; i++) {
hash_map[s[i]]++;
//一开始是小于m的，因此外面是小，while内是大。
while (hash_map.size() > m) {
hash_map[s[left]]--;
if (hash_map[s[left]] == 0) {
hash_map.erase(s[left]);
}
left++;
}
if (is_ok(hash_map, k)) {
res = max(res, i - left + 1);
}
}
}
return res;
}
};
分治
使用递归分而治之。
- 如何分：显然对于那些出现次数小于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;
}
};