LeetCode#395. 至少有K个重复字符的最长子串

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入: s = “aaabb”, k = 3

输出: 3

最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。 示例 2:

输入: s = “ababbc”, k = 2

输出: 5

最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。 通过次数10,974提交次数25,372

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：这道题好难想，要用分治解法，递归解决，然后再想想怎么减少递归次数来剪枝，限制递归的条件

class Solution { public: int longestSubstring(string s, int k) { //采用分治思想，需要确定断点 //用出现次数小于k的字符所在位置作为断点 map<char,int> m; vector<int> split; for(int i=0;i<s.length();i++){ m[s[i]]++; } //split用来找出断点 for(int i = 0;i<s.length();i++){ if(m[s[i]] < k){ split.push_back(i); } } //如果没有断点说明整个子串满足条件，则返回长度即可 if(split.size() == 0) return s.length(); //如果有断点就还要把长度作为断点 split.push_back(s.length()); //由断点来判断按照断点划分出来的子字符串是否可以满足条件 //条件就是其中所有的字符都是满足大于k的 //用left记录左边的断点，也就是左边不可能成为满足条件字串的下标 int left = -1; int ans = 0; for(int i=0;i<split.size();i++){ //当前的字串长度 int len = split[i] - left - 1; //判断该子串是否满足 //字串递归即可，解法是相同的,因此采用分治 //这里要怎么剪纸呢？ //限制递归条件，len大于k并且大于ans才进行递归 if(len >= k && len > ans) ans = max(ans,longestSubstring(s.substr(left+1,len),k)); left = split[i]; } return ans; } };