# Longest SubString with At Least K Repeating Characters

Oct 05, 2017

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Input: s = “aaabb”, k = 3

Output: 3

The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Input: s = “ababbc”, k = 2

Output: 5

The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

unordered_map<char,int> count;
for(auto c:s)
++count[c];


Input: s = “ababacb” k = 3

• 先遍历一遍计算整个串中出现的次数
• 然后开始从头遍历，找出一个t使得count[ s[t] ] < k
• 找到了，我们就分别计算s[i:t]和s[t+1:j]的最大长度即可
• 没找到，那么说明整个串是符合的，我们直接返回串长度即可
• 递归结束的条件就是当串长度比k小的时候啦。
string s;   //为了减少递归传递而设置的全局变量
int t;

int longestSubstring(string ss, int tt) {
if (tt <= 1) return ss.size();
s = ss;
t = tt;
unordered_map<char,int> count;
for(auto c:s)
++count[c];
return longestSubString(0,s.size(),count);
}

int longestSubString(int beg,int end,unordered_map<char,int> &imap ){
if (end - beg < t) return 0;
int j;
for(j = beg;j < end && imap[s[j]] >= t;j++)
/*do nothing*/;
if (j == end) return end - beg;
unordered_map<char,int> right;
for(int k = beg;k < j;k++){
--imap[ s[k] ];//重复利用imap，减少空间复杂度
++right[ s[k] ];
}
return max(longestSubString(beg,j,right),
longestSubString(j+1,end,imap));
}


int longestSubstring(string s, int k) {
if(s.size() == 0 || k > s.size())   return 0;
if(k == 0)  return s.size();
unordered_map<char,int> Map;
for(int i = 0; i < s.size(); i++){
Map[s[i]]++;
}
int idx =0;
while(idx <s.size() && Map[s[idx]] >= k)    idx++;
if(idx == s.size()) return s.size();
int left = longestSubstring(s.substr(0 , idx) , k);
int right = longestSubstring(s.substr(idx+1) , k);
return max(left, right);
}


int longestSubstring(string s, int k) {
int max_len = 0;
for (int first = 0; first+k <= s.size();) {
int count[26] = {0};
int mask = 0;
int max_last = first;
for (int last = first; last < s.size(); ++last) {
int i = s[last] - 'a';
count[i]++;
if (count[i]<k) mask |= (1 << i);
else   mask &= (~(1 << i));

if (mask == 0) {
max_len = max(max_len, last-first+1);
max_last = last;
}
}
first = max_last + 1;
}
return max_len;
}

LeetCodeLeetCode

Letter Combinations of a Phone Number

4Sum_2