每日一题 395 (滑动数组/递归)
文章目录
395. 至少有 K 个重复字符的最长子串
给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
输入:s = "aaabb", k = 3
输出:3
思路
- 采用递归的方式计算最长子串(需要是连续的)
- 如果某个字符次数小于k,则所有包含它的都不满足,可以划分
class Solution {
public:
int longestSubstring(string s, int k) {
if (s.size() < k) {
return 0;
}
unordered_map<char, int> um;
for (int i = 0; i < s.size(); i++) {
um[s[i]]++;
}
unordered_set chars(s.begin(), s.end());
for (char c : chars) {
vector<string> t;
if (um[c] < k) {
split(s, t, c);
int res = 0;
for (string st : t) {
res = max(res, longestSubstring(st, k));
}
return res;
}
}
return s.size();
}
void split(const string &s, vector<string> &sv, char flag = ' ') {
sv.clear();
istringstream iss(s);
string temp;
while (getline(iss, temp, flag)) {
sv.push_back(temp);
}
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论