C++で最も長く繰り返される文字の部分文字列と交換する

文字列テキストがあるとすると、文字列内の2つの文字を入れ替えることができます。文字が繰り返される最長の部分文字列の長さを見つける必要があります。したがって、入力が「ababa」の場合、結果は3になります。たとえば、最初のbを最後のaに交換するか、最後のbを最初のaに交換するかのように、最も長く繰り返される文字は「aaa」になるため、長さは次のようになります。 3。

これを解決するには、次の手順に従います-

• マップcntを定義し、ret：=1、j：=0、n：=テキストのサイズ、v：=0を定義し、xというセットを定義し、mという別のマップを作成します。mは各文字の頻度を保持します。テキストで。

• a：=*とb：=*

  を設定します

• 0からnの範囲のiの場合

  • cnt[text[i]]を1増やします

  • text[i]をx

    に挿入します

  • cnt [text [i]]が2の場合、

    • aが*の場合。次にa：=text [i]、それ以外の場合はb：=text [i]

  • aが*でなく、bも*でない場合、またはxのサイズが2より大きい場合

    • cnt[text[j]]を1減らします

    • cnt [text [j]]が1の場合、

      • text [j]がaの場合は、a：=*を設定し、そうでない場合はb：=*

        を設定します。

  • cnt [text [j]]が0の場合、xからtext[j]を削除します

  • より大きい：=a if cnt [a]> cnt [b]、それ以外の場合b

  • xのサイズが1またはm[greater]– cnt [greater]が0以外の場合、

    • ret：=retの最大値、i – j + 1

  • それ以外の場合、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