交换C ++中最长的重复字符子字符串
假设我们有一个字符串文本，因此我们可以交换字符串中的两个字符。我们必须找到带有重复字符的最长子字符串的长度。因此，如果输入是“ababa”，则结果将为3，就好像我们将第一个b与最后一个a交换，或者将最后一个b与第一个a交换一样，则最长的重复字符将为“aaa”，因此长度为3。
为了解决这个问题，我们将遵循以下步骤-
定义一个映射cnt，设置ret：=1，j：=0，n：=文本大小，v：=0，定义一个名为x的集合，并创建另一个名为m的映射，m将保存每个字符的频率在文本中。
设置a：=*和b：=*
当我在0到n的范围内
ret：=最大ret，i–j+1
将cnt[text[j]]减少1
如果cnt[text[j]]为1，则
如果text[j]是a，则设置a：=*，否则设置b：=*
如果a是*。然后a：=text[i]，否则b：=text[i]
将cnt[text[i]]增加1
在x中插入text[i]
如果cnt[text[i]]为2，则
如果a不是*并且b也不是*或x的大小大于2
如果cnt[text[j]]为0，则从x中删除text[j]
更大：=a，如果cnt[a]>cnt[b]，否则b
如果x的大小为1或m[greater]–cnt[greater]不为0，则
否则ret：=ret的最大值，i–j
返回ret。
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxRepOpt1(string text) {
int ret = 1;
map <char, int> cnt;
int j = 0;
int n = text.size();
int v = 0;
set <char> x;
map <char, int> m;
for(int i = 0; i < text.size(); i++)m[text[i]]++;
char a = '*', b ='*';
for(int i = 0; i < n; i++){
cnt[text[i]]++;
x.insert(text[i]);
if(cnt[text[i]] == 2){
if(a == '*'){
a = text[i];
}else{
b = text[i];
}
}
while(a != '*' && b != '*' || x.size() > 2){
cnt[text[j]]--;
if(cnt[text[j]] == 1) {
if(text[j] == a) {
a ='*';
}else{
b = '*';
}
}
if(cnt[text[j]] == 0) x.erase(text[j]);
j++;
}
char greater = cnt[a] > cnt[b] ? a : b;
if(x.size() == 1 || m[greater] - cnt[greater]){
ret = max(ret, i - j + 1);
}else{
ret = max(ret, i - j);
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.maxRepOpt1("ababa"));
}输入项
"ababa"
输出结果
3