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