交换C ++中最长的重复字符子字符串

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串文本，因此我们可以交换字符串中的两个字符。我们必须找到带有重复字符的最长子字符串的长度。因此，如果输入是“ 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

    以上是 交换C ++中最长的重复字符子字符串 的全部内容， 来源链接： utcz.com/z/352609.html

    回到顶部