NC364. 至少有 K 个重复字符的最长子串
描述
给定一个长度为 n 的字符串 s ，请你找出 s 的最长子串，这个子串满足所有字符都出现大于等于 k 次。请你返回这个子串的长度。
数据范围：
，字符串中仅出现小写英文字母
示例1
输入:
"aaabb",3
输出:
3
示例2
输入:
"aaabb",2
输出:
5
NC364. 至少有 K 个重复字符的最长子串
描述
示例1
输入:
"aaabb",3
输出:
3
示例2
输入:
"aaabb",2
输出:
5
C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-08-03
class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size();
if (k < 2) return n;
if (n < k) return 0;
int m[26];
memset(m,0,sizeof(m));
for(auto c : s){
m[c-'a']++;
}
int i = 0;
for(;i<s.length();i++){
cout<<i;
if(m[s[i]-'a'] < k) break;
}
if(i==s.length()) return s.length();
int left = longestSubstring(s.substr(0,i),k);
for( ;i<s.length();i++){
if(m[s[i]-'a'] >= k) break;
}
int right = longestSubstring(s.substr(i),k);
return max(left,right);
}
};
// class Solution {
// public:
// int longestSubstring(string s, int k) {
// int n = s.size();
// if (k < 2) return n;
// if (n < k) return 0;
// int m[26] = {0};
// for (auto c : s) ++m[c-'a'];
// int i = 0;
// while (i < n && m[s[i]-'a'] >= k) ++i;
// if (i == n) return n;
// int left = longestSubstring(s.substr(0, i), k);
// while (i < n && m[s[i]-'a'] < k) ++i;
// int right = longestSubstring(s.substr(i), k);
// return max(left, right);
// }
// };
C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-04-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int longestSubstring(string s, int k) {
// write code here
map<char,int>m;
int len=s.size();
int l=0;
int r=0;
int maxvalue=-2147483648;
map<char,int>m1;
for(int i=0;i<s.size();i++){
m1[s[i]]++;
}
bool flag1=false;
for(auto k1:m1){
if(k1.second>=k){
flag1=true;
break;
}
}
if(flag1==false){
return 0;
}
while(l!=len){
if(r!=len){
m[s[r]]++;
bool flag=false;
for(auto k1:m){
if(k1.second<k){
flag=true;
break;
}
}
if(flag==false){
maxvalue=max(maxvalue,r-l+1);
}
r++;
}else{
bool flag=false;
for(auto k1:m){
if(k1.second<k){
flag=true;
break;
}
}
if(flag==false){
maxvalue=max(maxvalue,r-1-l+1);
break;
}
l++;
r=l;
m.clear();
}
}
return maxvalue;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 440KB, 提交时间: 2022-07-08
class Solution {
public:
int longestSubstring(string s, int k) {
map<char, int>p;
map<char, int>q;
int h = s.size();
int a = 0;
int b = 0;
int maxvalue = -2147483648;
for (int i = 0; i < h; i++) {
q[s[i]]++;
}
bool g = false;
for (auto j : q) {
if (j.second >= k) {
g = true;
break;
}
}
if (g == false) {
return 0;
}
while (a != h) {
if (b != h) {
p[s[b]]++;
bool f = false;
for (auto k1 : p) {
if (k1.second < k) {
f = true;
break;
}
}
if (f == false) {
maxvalue = max(maxvalue, b - a + 1);
}
b++;
} else {
bool f = false;
for (auto k1 : p) {
if (k1.second < k) {
f = true;
break;
}
}
if (f == false) {
maxvalue = max(maxvalue, b - 1 - a + 1);
break;
}
a++;
b = a;
p.clear();
}
}
return maxvalue;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 440KB, 提交时间: 2022-06-15
#include <bits/stdc++.h>
using namespace std;
//#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x) freopen("d:/oj/" #x ".in", "r", stdin) //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
public:
// "cadabb",2
int longestSubstring(string str_, int nMinK) {
if (str_.length() < nMinK) {
return 0;
}
size_t nMaxSubLen = 0;
queue<string> quString;
quString.push(str_);
PF("push=%s\n", str_.c_str());
while(!quString.empty()) {
auto subtmp = quString.front(); quString.pop();
// aabbccdeeeee
map<char, int> mapFreq;
for (auto ch : subtmp) mapFreq[ch]++;
for (auto[ch, num] : mapFreq) PF("map ={%c,%d}\n", ch,num);
int nStart = 0;
int nEnd = 0;
for (; nEnd < subtmp.length(); nEnd++) {
// 字符数量不够,分割
// aaabbbcdddffff
// ^
PF("=== %c, %d, min=%d\n", subtmp[nEnd], mapFreq[subtmp[nEnd]], nMinK);
if (mapFreq[subtmp[nEnd]] < nMinK) {
PF("freq=%c,%d\n", subtmp[nEnd], nEnd);
int tmpLen = nEnd - nStart;
if (tmpLen > 0 && tmpLen >= nMinK) {
quString.push(subtmp.substr(nStart, tmpLen));
PF("push=%s, [%d,%d\n", subtmp.substr(nStart, tmpLen).c_str(), nStart, nEnd);
}
nStart = nEnd + 1; // next
PF("next=%d,%d\n", nStart, nEnd);
}
}
int tmpLen = nEnd - nStart;
if (nStart > 0 && tmpLen > 0 && tmpLen >= nMinK) {
quString.push(subtmp.substr(nStart, tmpLen));
PF("push=%s, %d,%d,%d\n", subtmp.substr(nStart, tmpLen).c_str(), tmpLen, nStart, nEnd);
}
if (nStart == 0) {
nMaxSubLen = std::max(nMaxSubLen, subtmp.length());
}
}
return nMaxSubLen;
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 424KB, 提交时间: 2022-07-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int dfs(const string& s, int l, int r, int k) {
vector<int> cnt(26, 0);
for (int i = l; i <= r; i++) {
cnt[s[i] - 'a']++;
}
char split = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0 && cnt[i] < k) {
split = i + 'a';
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ret = 0;
while (i <= r) {
while (i <= r && s[i] == split) {
i++;
}
if (i > r) {
break;
}
int start = i;
while (i <= r && s[i] != split) {
i++;
}
int length = dfs(s, start, i - 1, k);
ret = max(ret, length);
}
return ret;
}
int longestSubstring(string s, int k) {
// write code here
/* 每次递归：统计每个字符的出现次数 存入freq[]
遍历每一个字符，遇到freq < k的就把字符串拆分成左右两边分别求解，取max
比如 aaabbbcdddefff,对于c拆分 -> aaabbb, dddefff
aaabbb会直接return 6，dddefff继续对e拆分 -> ddd, fff*/
int n = s.length();
return dfs(s, 0, n - 1, k);
}
};