需求
找到给定字符串(由小写字符组成)中的最长子串 T , 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入:
s = "aaabb", k = 3
输出:
3
最长子串为 "aaa" ,其中 'a' 重复了 3 次。
示例 2:
输入:
s = "ababbc", k = 2
输出:
5
最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。
思路:分治,递归
遍历一遍字符串,找到各个字符出现的位置并统计各个字符出现的次数,若字符出现次数小于k,则该字符出现的位置即为分割点。
找到所有分割点,排序分割点,对相邻分割点之间的区间递归调用此算法。得出最大值,完成。
时间复杂度:分治一般是O(nlogn)。这里分析下最坏情况,每一遍扫描或者找到分割点,进行下一次递归,或者没有找到分割点,结束。所以最坏的情况下是每次找到一个分割点,即一次删除一个元素,而删除一个元素时间复杂度为O(n),整体最坏情况下时间复杂度为O(n^2)。
代码
class Solution {
public:
int longestSubstring(string s, int k) {
if(s.size()<k) return 0;
map<char,vector<int> > pos;
vector<int> span;
for(int i=0;i<s.size();++i){
if(pos.count(s[i])>0){
pos[s[i]].push_back(i);
}else{
pos[s[i]]={i};
}
}
for(auto kv:pos){
auto v=kv.second;
if(v.size()<k){
for(auto& i:v){
span.push_back(i);
}
}
}
if(span.size()<1) return s.size();
sort(span.begin(),span.end());
int i=0,j;
int ret=0;
for(int m=0;m<span.size();++m){
j=span[m];
ret=max(ret,findSub(s,k,i,j));
i=j+1;
}
ret=max(ret,findSub(s,k,j+1,s.size()));
return ret;
}
int findSub(string s,int k,int start,int end){
if(end-start<k) return 0;
return longestSubstring(s.substr(start,end-start),k);
}
};