Khái niệm
Đối với một chuỗi đã cho, hãy xác định palindrome dài nhất có thể được hình thành bằng cách xóa hoặc xáo trộn các ký tự khỏi chuỗi. Cuối cùng chỉ trả về một palindrome nếu nó đã quan sát thấy rằng có nhiều chuỗi palindrome có độ dài dài nhất.
Đầu vào
pqr
Đầu ra
p OR q OR r
Đầu vào
ppqqrr
Đầu ra
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
Đầu vào
pqp
Đầu ra
pqp
Phương pháp
Ở đây, Chúng tôi có thể phân vùng bất kỳ chuỗi palindromic nào thành ba phần - phần xin, phần giữa và phần cuối. Với chuỗi ký tự trọng lượng có độ dài lẻ giả sử là 2n + 1, ở đây 'cầu xin' bao gồm n ký tự đầu tiên của chuỗi, 'giữa' chỉ bao gồm 1 ký tự có nghĩa là (n + 1) ký tự thứ và 'kết thúc' bao gồm n ký tự cuối cùng của chuỗi palindromic. Đối với chuỗi palindromic có độ dài chẵn 2n, sẽ luôn trống ở 'giữa'. Chúng tôi đã biết rằng ‘end’ sẽ đảo ngược với ‘please’ theo thứ tự đối với chuỗi là palindrome. Bây giờ khái niệm là triển khai quan sát ở trên trong giải pháp của chúng tôi. Vì cho phép xáo trộn các ký tự, không có vấn đề gì về thứ tự của các ký tự trong chuỗi đầu vào. Bây giờ trước tiên chúng ta có được tần số của mỗi ký tự trong chuỗi đầu vào. Sau đó, tất cả các ký tự có số chẵn (giả sử 2n) trong chuỗi đầu vào sẽ là một phần của chuỗi đầu ra vì wecan dễ dàng đặt n ký tự trong chuỗi "xin" và n ký tự khác trong chuỗi "kết thúc" (với sự trợ giúp của việc bảo toàn thứ tự palindromic). Đối với các ký tự có số lần xuất hiện lẻ (giả sử 2n + 1), ở đây, chúng tôi điền "mid" bằng một trong tất cả các ký tự như vậy và 2n ký tự còn lại được chia thành hai nửa và được thêm vào ở đầu và cuối.
Ví dụ
// C++ program to find the longest palindrome by removing
// or shuffling characters from the given string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find the longest palindrome by removing
// or shuffling characters from the given string
string findLongestPalindrome(string str1){
// Indicated to stores freq of characters in a string
int count1[256] = { 0 };
// Determine freq of characters in the input string
for (int i = 0; i < str1.size(); i++)
count1[str1[i]]++;
// Shows any palindromic string consisting of three parts
// beg1 + mid1 + end1
string beg1 = "", mid1 = "", end1 = "";
//Here solution assumes only lowercase characters are
// present in string. We can easily extend this
// to consider any set of characters
for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
// Now if the current character freq is odd
if (count1[ch1] & 1){
// Here mid1 will contain only 1 character. It
// will be overridden with next character
// with odd freq
mid1 = ch1;
// Here decrement the character freq to make
// it even and consider current character
// again
count1[ch1--]--;
}
// Here if the current character freq is even
else{
// Now if count is n(an even number), push
// n/2 characters to beg string and rest
// n/2 characters will form part of end
// string
for (int i = 0; i < count1[ch1]/2 ; i++)
beg1.push_back(ch1);
}
}
// Here end will be reverse of beg
end1 = beg1;
reverse(end1.begin(), end1.end());
// Now return palindrome string
return beg1 + mid1 + end1;
}
// Driver code
int main(){
string str1 = "pqqprrs";
cout << findLongestPalindrome(str1);
return 0;
} Đầu ra
pqrsrqp