Description:
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.
Example:
Example 1:
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Link:
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/
解題方法：
用遞歸的方法，現(xiàn)在當前字符串中找出出現(xiàn)次數(shù)小于k次的字符疯暑，根據(jù)不合格的字符將當前字符分割成一個個子串蔓彩。重復分割過程舰涌，找出最大的合格子串長度打洼。
Time Complexity：
O(26N) = O(N)
完整代碼：
int longestSubstring(string s, int k)
{
int maxLen = 0;
if(!s.size())
return maxLen;
vector<int> record(26, 0);
for(char ch: s)
{
record[ch - 'a']++;
}
unordered_set<char> invalid;
for(int i = 0; i < s.size(); i++)
{
if(record[s[i] - 'a'] < k)
invalid.insert(s[i]);
}
if(invalid.empty())
return s.size();
int maxlen = 0, last = 0;
for(int i = 0; i < s.size(); i++)
{
if(invalid.find(s[i]) != invalid.end())
{
maxlen = max(maxlen, longestSubstring(s.substr(last, i - last), k));
last = i + 1;
}
}
maxlen = max(maxlen, longestSubstring(s.substr(last), k));
return maxlen;
}
