Cho chuỗi 'str' độ dài bất kỳ. Nhiệm vụ: sắp xếp lại ký tự thành chuỗi palindrome nếu có thể, không thêm/xóa ký tự. 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 ký tự tạo palindrome: nitin
Giải thích - Sắp xếp "itnin" thành "nitin" (palindrome).
Đầu vào - string str = "baaaba"
Đầu ra - Sắp xếp ký tự tạo palindrome: aabbaa
Giải thích - Sắp xếp "baaaba" thành "aabbaa" (palindrome).
Phương pháp sử dụng trong chương trình dưới đây
Nhập chuỗi str, tính length.
Gọi Rearrangement(str, length).
Trong hàm Rearrangement:
unordered_map
int total=0 đếm ký tự xuất hiện số lần lẻ.
char ch lưu ký tự lẻ (nếu có).
string str1, str2 xây dựng nửa đầu và nửa sau.
Duyệt str: um[str[i]]++.
Duyệt um: nếu it.second%2!=0 → total++, ch=it.first.
Nếu total>1 hoặc (total==1 và length chẵn) → trả về 0 (không thể).
Duyệt um: tạo chuỗi it.second/2 lần it.first, str1 += chuỗi, str2 = chuỗi + str2.
Nếu total==1 trả về str1 + ch + str2, ngược lại str1 + str2.
In kết quả.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; string Rearrangement(string str, int length){ unordered_map<char, int> um; int total = 0; char ch; string str_1 = ""; string str_2 = ""; for (int i = 0; i < length; i++){ um[str[i]]++; } for(auto it : um){ if(it.second % 2 != 0){ total++; ch = it.first; } } if(total > 1 || total == 1 && length % 2 == 0){ return 0; } for(auto it : um){ string str(it.second / 2, it.first); str_1 = str_1 + str; str_2 = str + str_2; } if(total == 1){ return str_1 + ch + str_2; } else{ return str_1 + str_2; } } int main(){ string str = "itnin"; int length = str.size(); cout<<"Sắp xếp ký tự tạo palindrome nếu có thể: "<<Rearrangement(str, length); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Sắp xếp ký tự tạo palindrome nếu có thể: nitin