Cho chuỗi 'str' độ dài bất kỳ. Nhiệm vụ là sắp xếp lại các ký tự sao cho số lượng chuỗi con palindrome là nhiều nhất, không thêm/xóa ký tự. Chuỗi palindrome đọc từ đầu và cuối giống nhau.
Các trường hợp đầu vào/đầu ra
Đầu vào - string str = "itnin"
Đầu ra - Sắp xếp lại chuỗi để tối đa hóa số chuỗi con palindrome: iinnt.
Giải thích - Sắp xếp ký tự để tạo chuỗi có nhiều chuỗi con palindrome nhất. Kết quả: 'iinnt'.
Đầu vào - string str = "abaaaabb"
Đầu ra** - Sắp xếp lại chuỗi để tối đa hóa số chuỗi con palindrome: aaaaabbb.
Giải thích - Kết quả: 'aaaaabbb'.
Phương pháp sử dụng trong chương trình dưới đây
Nhập chuỗi str, tính độ dài length.
Gọi hàm Rearr_string(str, length).
Trong hàm Rearr_string:
Khai báo mảng int arr[26] = {0} đếm tần suất ký tự.
String temp = "".
Vòng for i=0 đến length-1: arr[str[i]-'a']++.
Vòng for i=0 đến 25: vòng for j=0 đến arr[i]-1: temp += char(97+i).
Trả về temp (chuỗi ký tự sắp xếp theo thứ tự bảng chữ cái).
In kết quả.
Ví dụ mã
#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<<"Sắp xếp lại chuỗi để tối đa hóa số chuỗi con palindrome: "<<Rearr_string(str, length); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Sắp xếp lại chuỗi để tối đa hóa số chuỗi con palindrome: iinnt