Susun semula rentetan untuk memaksimumkan bilangan subrentetan palindromik dalam C++

Kami mendapat rentetan "str" ​​​​dari mana-mana panjang tertentu. Tugasnya adalah untuk menyusun semula aksara sedemikian rupa sehingga, tanpa menambah atau mengalih keluar aksara daripada rentetan input yang diberikan, akan terdapat subrentetan terbesar yang menjadi rentetan palindrom. Rentetan palindrom ialah rentetan aksara yang disusun sedemikian rupa sehingga bunyinya sama dari awal hingga akhir.

Mari kita lihat pelbagai senario input dan output untuk situasi ini -

input− rentetan str = "itnin"

output− Menyusun semula rentetan untuk memaksimumkan bilangan rentetan kecil palindromik.

Input− string str = "abaaaabb"

Output − Menyusun semula rentetan untuk memaksimumkan bilangan subrentetan palindromik ialah: aaaaabbb.

Penjelasan − Kami memberikan pembolehubah jenis rentetan, seperti str. Sekarang kita akan menyusun semula aksara rentetan input untuk menjadikannya rentetan palindrom maksimum dan kembalikan "TIDAK MUNGKIN" jika ini tidak mungkin. Jadi output yang diberikan rentetan input ialah aaaaabbb'

Kaedah yang digunakan dalam program di bawah adalah seperti berikut

• Masukkan pembolehubah rentetan Katakan anda memasukkan str dan mengira saiz rentetan dan menyimpannya dalam pembolehubah yang dipanggil panjang.

• Hantar data ke fungsi Rearr_string(str, length).

• Di dalam fungsi Rearr_string(str, length)

  • isytiharkan tatasusunan jenis integer bersaiz 26 sebut arr[26] dan mulakan dengan 0.

  • Isytiharkan pembolehubah sementara "temp" jenis rentetan.

  • Mulakan gelung FOR dari i ke 0 sehingga i kurang daripada panjang. Di dalam gelung, tetapkan arr[str[i] - 'a']++.

  • Mulakan gelung FOR dari i ke 0 sehingga i kurang daripada 26. Di dalam gelung, mulakan gelung FOR lain dari j hingga 0 sehingga j kurang daripada arr[i]. Di dalam gelung, tetapkan temp kepada temp + (char)(97 + i).

  • Suhu balik.

• Cetak hasilnya.

Contoh

#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] - &#39;a&#39;]++;
   }
   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;
}

Output

Jika kita menjalankan kod di atas, ia akan menghasilkan output berikut

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

Atas ialah kandungan terperinci Susun semula rentetan untuk memaksimumkan bilangan subrentetan palindromik dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!