Sắp xếp lại chuỗi để tối đa hóa số chuỗi con palindromic trong C ++

Chúng tôi được cung cấp với một chuỗi ‘str’ có độ dài bất kỳ. Nhiệm vụ là sắp xếp lại các ký tự theo cách mà sẽ có tối đa các chuỗi con sẽ là một chuỗi palindrome mà không cần thêm hoặc bớt một ký tự khỏi chuỗi đầu vào đã cho. Chuỗi Palindrome là chuỗi trong đó các ký tự được sắp xếp theo cách mà chúng phát âm giống nhau từ đầu và cuối.

Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -

Đầu vào - string str ="itnin"

Đầu ra - Sắp xếp lại chuỗi để tối đa số chuỗi con palindromic là:iinnt.

Giải thích - Chúng tôi được cung cấp một biến kiểu chuỗi, giả sử, str. Bây giờ chúng ta sẽ sắp xếp lại các ký tự của một chuỗi đầu vào theo cách mà nó sẽ là một chuỗi palindrome tối đa và nếu không thể thực hiện được thì nó sẽ trả về "KHÔNG CÓ THỂ". Vì vậy, đầu ra với chuỗi đầu vào đã cho là ‘iinnt.’

Đầu vào - chuỗi str ="abaaaabb"

Đầu ra - Sắp xếp lại chuỗi để tối đa số chuỗi con palindromic là:aaaaabbb.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Nhập một biến kiểu chuỗi, giả sử, str và tính toán kích thước của một chuỗi và lưu trữ nó trong một biến có độ dài được đặt tên.
Truyền dữ liệu vào hàm Rearr_string (str, length).
Bên trong hàm Rearr_string (str, length)
- Khai báo một mảng kiểu số nguyên có kích thước 26, giả sử arr [26] và khởi tạo nó bằng 0.
- Khai báo một biến tạm thời 'temp' của kiểu chuỗi.
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn độ dài. Bên trong vòng lặp, đặt arr [str [i] - 'a'] ++.
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn 26. Bên trong vòng lặp, bắt đầu một vòng lặp FOR khác từ j đến 0 cho đến khi j nhỏ hơn arr [i]. Bên trong vòng lặp, đặt nhiệt độ thành temp + (char) (97 + i).
- Nhiệt độ trở lại.
In kết quả.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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