文字列を再配置して、C++のパリンドローム部分文字列の数を最大化します

任意の長さの文字列「str」が与えられます。タスクは、指定された入力文字列に文字を追加または削除せずに、回文文字列になる最大の部分文字列が存在するように文字を再配置することです。回文文字列は、文字が最初から最後まで同じように発音されるように配置された文字列です。

このためのさまざまな入出力シナリオを見てみましょう-

入力 − string str ="itnin"

出力 −パリンドローム部分文字列の数を最大化するための文字列の再配置は次のとおりです。iinnt。

説明 −文字列型変数、たとえばstrが与えられます。次に、入力文字列の文字を、最大の回文文字列になるように再配置します。それが不可能な場合は、「NOTPOSSIBLE」を返します。したがって、指定された入力文字列を使用した出力は「iinnt」です。

入力 − string str ="abaaaabb"

出力 −パリンドローム部分文字列の数を最大化するための文字列の再配置は次のとおりです。aaaaabbb。

説明 −文字列型変数、たとえばstrが与えられます。次に、入力文字列の文字を、最大の回文文字列になるように再配置します。それが不可能な場合は、「NOTPOSSIBLE」を返します。したがって、指定された入力文字列を使用した出力はaaaaabbb’

以下のプログラムで使用されているアプローチは次のとおりです

• 文字列型の変数（たとえば、str）を入力し、文字列のサイズを計算して、variableという名前の長さに格納します。

• データを関数Rearr_string（str、length）に渡します。

• 関数Rearr_string（str、length）

  の内部

  • サイズ26の整数型の配列を宣言します。たとえば、arr [26]とし、0で初期化します。

  • 文字列型の一時変数「temp」を宣言します。

  • iが長さより小さくなるまで、ループFORをiから0まで開始します。ループ内で、arr [str[i]-'a']++を設定します。

  • ループFORをiから0まで開始してiが26未満になるまで。ループ内で、jからjまでがarr[i]未満になるまで別のループFORを開始します。ループ内で、tempをtemp +（char）（97 +i）に設定します。

  • 戻り温度。

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
string Rearr_string(string str, int length){
   int arr[26] = { 0 };
   string temp = "";
   for(int i = 0; i < length; i++){
      arr[str[i] - 'a']++;
   }
   for(int i = 0; i < 26; i++){
      for(int j = 0; j < arr[i]; j++){
         temp = temp + (char)(97 + i);
      }
   }
   return temp;
}
int main(){
   string str = "itinn";
   int length = str.length();
   cout<<"Rearrangement of the string to maximize the number of palindromic substrings is: "<<Rearr_string(str, length);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Rearrangement of the string to maximize the number of palindromic substrings is: iinnt