暴力求解所有区间情况，超时。。。==
class Solution { public: int longestSubstring(string s, int k) { int maxLength=0; map<int,int> count; for(int i=0;i<s.size();i++) count[s[i]]++; set<int> wrongNum; for(map<int,int>::iterator it=count.begin();it!=count.end();it++) { if(it->second<k) wrongNum.insert(it->first); } //3 for(int i=0;i<s.size();i++) { map<int,int> tempCount=count; set<int> tempWrongNum=wrongNum; for(int j=s.size()-1;j>=i;j--) { if(tempWrongNum.empty()) { maxLength=max(maxLength,j-i+1); break; } tempCount[s[j]]--; if(tempCount[s[j]]==0) tempWrongNum.erase(s[j]); else if(tempCount[s[j]]<k) tempWrongNum.insert(s[j]); else{} } count[s[i]]--; if(count[s[i]]==0) wrongNum.erase(s[i]); else if(count[s[i]]<k) wrongNum.insert(s[i]); else{} } return maxLength; } };参考discuss，采用分治的思想求解，减少时间的复杂度，不用再计算所有的区间。 主要利用的时，对于出现次数小于k的那些位置，一定不再substr的区间上，可以将它们作为分界点，再计算左右两部分区间的max。
class Solution { public: int longestSubstring(string s, int k) { if(s.size()==0) return 0; int maxLength=0; map<int,int> count; for(int i=0;i<s.size();i++) count[s[i]]++; char wrong; map<int,int>::iterator it; for(it=count.begin();it!=count.end();it++) { if(it->second<k) { wrong=it->first; break; } } if(it==count.end()) return s.size(); int mid; for(int i=0;i<s.size();i++) { if(s[i]==wrong) { int left=longestSubstring(s.substr(0,i), k); int right=longestSubstring(s.substr(i+1), k); return max(left,right); } } } };