链接395. 至少有 K 个重复字符的最长子串 - 力扣LeetCode我们来思考一下什么样的情况可能可以构成连续的子串每个字符都出现了至少k次什么情况下又构不成很显然如果字符串里有字符在整个串里都没出现k次那么含有这个字符的子串一定是不可能成立的。那是不是子串里每个字符串都出现了k次就可以呢 其实也不是的举一个例子来说明如:s abbccddadcbbb k 3其中s[1:6]中的b,c,d都在s中出现了3次以上那么s[1:6]是否是一个满足条件的子串呢显然不是因为b,c,d的第k次出现被一个不可能包含在满足条件的子串中的字符a隔开了。而左右两端的每个子串的出现条件就此应该重新计算而这个计算问题是否和原来的问题一致呢进而想到了分治的算法。题解395. 至少有 K 个重复字符的最长子串 - 力扣LeetCodeclass Solution { public: int longestSubstring(string s, int k) { if(s.size()0) return 0; return cnt(s, 0, s.size()-1, k); } int cnt(const std::string s, int left, int right, int k) { std::unordered_mapchar, int count; // 统计字符串从left到right的个数 for(int i left; i right; i) { count[s[i]]; } // 找到字符串中字符k的开始 for(; left right; left) { if(count[s[left]] k) { break; } } // 找到字符串中字符k的结尾 for(; right left; --right) { if(count[s[right]] k) { break; } } // 如果[left, right] k if(right-left1 k) { return 0; } int partition left; // 判断[left, right]之间的字符数量是不是都k次 for(; partition right; partition) { if(count[s[partition]] k) { break; } } // [left, right]之间的字符数量都k次 if(partition right) { return right-left1; } // 分治找到字符串 return max(cnt(s, left, partition-1, k), cnt(s, partition1, right, k)); } };class Solution { public: int longestSubstring(string s, int k) { if (s.size() k) return 0; unordered_setchar chars(s.begin(), s.end()); unordered_mapchar, int counter; for (char c : s) counter[c] ; for (char c : chars) { vectorstring t; if (counter[c] k) { split(s, t, c); int res 0; for (string tn : t) { res max(res, longestSubstring(tn, k)); } return res; } } return s.size(); } void split(const string s, vectorstring sv,const char flag ) { sv.clear(); istringstream iss(s); string temp; while (getline(iss, temp, flag)) { sv.push_back(temp); } } };class Solution { public: int longestSubstring(string s, int k) { int len s.size(); if (len 0) { return 0; } int result 0; for (int i 1; i 26; i) { result max(result, calc(s, k, i)); } return result; } int calc(const string s, int k, int len) { unordered_mapchar, int table; // 不同字符串的个数 int valid 0; // 到达k数量字符的个数 int j 0; int result 0; for (int i 0; i s.size(); i) { while (j s.size() (table.size() len || table.count(s[j]))) { table[s[j]]; if (table[s[j]] k) { valid; } j; } if (valid table.size()) { result max(result, j - i); } if (--table[s[i]] k - 1) { --valid; } if (table[s[i]] 0) { table.erase(s[i]); } } return result; } };class Solution { public: int longestSubstring(string s, int k) { int len s.size(); if (len 0) { return 0; } int result 0; for (int i 1; i 26; i) { result max(result, calc(s, k, i)); } return result; } int calc(const string s, int k, int num) { unordered_mapchar, int table; int valid 0; int j 0; int result 0; for (int i 0; i s.size(); i) { while (j s.size() table.size() num) { table[s[j]]; if (table[s[j]] k) { valid; } j; } if (table.size() num 1) { // 情况 A超了一种字符最后加入的是 s[j-1]一定是新字符 // 有效窗口是 [i, j-2]长度 j - i - 1 // 需要剩下 num 种字符都满足 k if (table[s[j-1]] k valid num) { result max(result, j - i - 1); } } else { // 情况 Bj 到末尾了table.size() num // 有效窗口是 [i, j-1]长度 j - i if (table.size() num valid num) { result max(result, j - i); } } // 左指针右移 char c s[i]; if (table[c] k) { --valid; } --table[c]; if (table[c] 0) { table.erase(c); } } return result; } };问题背景题目要求找到一个子串使得子串中的每个字符都至少出现 k 次。我们希望找到满足条件的最长子串。为什么难以确定何时收缩窗口滑动窗口算法的核心是通过动态调整窗口的大小来寻找满足条件的子串。然而在这个问题中我们面临一个困境当窗口中某些字符的出现次数不足 k 次时我们无法确定是否应该收缩窗口。因为如果继续扩大窗口可能会让这些字符的出现次数达到 k 次从而满足条件。但如果一直扩大窗口又会导致窗口变得过大失去效率。如何通过约束条件解决问题为了有效利用滑动窗口算法我们需要引入一个额外的约束条件来帮助我们决定何时收缩窗口。具体来说我们可以引入一个参数 count表示窗口中允许存在的不同字符的种类数。这样问题就转化为求每个字符都出现至少 k 次且仅包含 count 种不同字符的最长子串。约束条件count的作用明确窗口的边界通过限制窗口中不同字符的种类数我们可以明确何时需要收缩窗口。当窗口中不同字符的种类数超过 count 时就必须收缩窗口直到窗口中不同字符的种类数不超过 count。简化问题将问题分解为多个子问题每个子问题对应一个特定的 count 值。通过遍历所有可能的 count 值从 1 到字符串中不同字符的总数我们可以找到满足条件的最长子串。