交换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