LeetCode 395. 至少有K个重复字符的最长子串（分治）数据结构与算法Michael是个半路程序员-

1. 题目

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

示例 1: 输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。  示例 2: 输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。 

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

2. 解题

• 找出字符串中次数小于 k 的，他们不能出现在答案中
• 以他们的位置把字符串切开，递归求解子问题
• 当一个子串中，字符计数都>= k 时，更新最大长度
• 剪枝，当前处理的字符串长度 <= 最大长度时，不再递归处理

class Solution { int maxlen = 0; public: int longestSubstring(string s, int k) { if(s.size() <= maxlen)//剪枝 return 0; int count[26] = {0}, i, left = 0; for(i = 0; i < s.size(); ++i)       count[s[i]-'a']++;      vector<int> split; for(i = 0; i < s.size(); ++i) { if(count[s[i]-'a'] > 0 && count[s[i]-'a'] < k)        split.push_back(i);//不能出现的字符位置 } if(split.empty())       maxlen = max(maxlen, int(s.size()));//没有切分位置，满足题意 for(i = 0; i < split.size(); ++i) { longestSubstring(s.substr(left, split[i]-left), k);             left = split[i]+1; if(i == split.size()-1 && left < s.size()) longestSubstring(s.substr(left, s.size()-left), k); } return maxlen; } }; 

8 ms 6.8 MB