题目来源
给一个字符串，以及一个数字k，求该字符串子串中每个字符出现的频次都大于等于k。
还是没有想法。
看了下讨论区，就是先遍历一遍，得出各个字符的频次，然后再遍历，找到第一个不符合的。然后分割成前后两块，再进行同样的操作。
能过，不过时间复杂度还是比价高的，平均复杂度应该是O(nlogn)。
代码如下：
class Solution {
public:
int longestSubstring(string s, int k) {
int len = s.size();
int maps[26] = {0};
for (int i=0; i<len; i++)
maps[s[i]-'a']++;
int splitPos = 0;
while (splitPos < len && maps[s[splitPos] - 'a'] >= k)
splitPos++;
if (splitPos == len)
return len;
int left = longestSubstring(s.substr(0, splitPos), k);
int right = longestSubstring(s.substr(splitPos + 1), k);
return max(left, right);
}
};
这个复杂度是O(n)，具体的话因为应该是O(26*n)。因为最多递归26次，每次至少去除了一个字母。每层递归的复杂度应该是O(n)。
class Solution {
public:
int longestSubstring(string s, int k) {
return longestSubstring_recur(s, k, 0, s.size());
}
int longestSubstring_recur(const string& s, int k, int start, int end)
{
int count[26] = {0};
for (int i=start; i<end; i++)
count[s[i] - 'a']++;
int maxLen = 0;
for (int i=start; i<end; ) {
while (i < end && count[s[i] - 'a'] < k)
i++;
if (i == end)
break;
int moreThanK = i;
while (moreThanK < end && count[s[moreThanK] - 'a'] >= k)
moreThanK++;
if (i == start && moreThanK == end)
return end - start;
maxLen = max(maxLen, longestSubstring_recur(s, k, i, moreThanK));
i = moreThanK;
}
return maxLen;
}
};
