难度中等351
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例 1：
输入：s = "aaabb", k = 3 输出：3 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2：
输入：s = "ababbc", k = 2 输出：5 解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
提示：
1 <= s.length <= 104-
s仅由小写英文字母组成 1 <= k <= 105
题解：分治+字符串分割
- 统计所有字符出现次数, 找到出现次数小于K次的所有字符
- 用这些频率小于k的字符作为切割点, 将str切割为更小的子串进行处理
class Solution {
public:
int longestSubstring(string s, int k) {
int ch[26] = { 0 };
for (auto i : s) {
ch[i - 'a'] ++;
}
string split_ch = "";
for (int i = 0; i < 26; ++i) {
if (ch[i] > 0 && ch[i] < k)
{
split_ch += (i + 'a');
break;
}
}
if (split_ch == "")
return s.length();
vector<string>split_s = split3(s, split_ch[0]);
int res = 0;
for (auto i : split_s) {
res = max(res, longestSubstring(i, k));
}
return res;
}
vector<string> split(const string &str, const string &pattern)
{
vector<string> res;
if (str == "")
return res;
//在字符串末尾也加入分隔符，方便截取最后一段
string strs = str + pattern;
size_t pos = strs.find(pattern);
while (pos != strs.npos)
{
string temp = strs.substr(0, pos);
res.push_back(temp);
//去掉已分割的字符串,在剩下的字符串中进行分割
strs = strs.substr(pos + 1, strs.size());
pos = strs.find(pattern);
}
return res;
}
vector<string> split3(const string &str, const char pattern)
{
vector<string> res;
stringstream input(str); //读取str到字符串流中
string temp;
//使用getline函数从字符串流中读取,遇到分隔符时停止,和从cin中读取类似
//注意,getline默认是可以读取空格的
while(getline(input, temp, pattern))
{
res.push_back(temp);
}
return res;
}
};