แนวคิด
สำหรับสตริงที่กำหนด ให้กำหนดพาลินโดรมที่ยาวที่สุดที่สามารถเกิดขึ้นได้โดยการเอาหรือสับเปลี่ยนอักขระออกจากสตริง ในที่สุดก็ส่งคืน palindrome เพียงอันเดียวหากพบว่ามีสตริง palindrome ที่ยาวที่สุดหลายอัน
อินพุต
pqr
ผลลัพธ์
p OR q OR r
อินพุต
ppqqrr
ผลลัพธ์
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
อินพุต
pqp
ผลลัพธ์
pqp
วิธีการ
ที่นี่ เราสามารถแบ่งสตริงพาลินโดรมใดๆ ออกเป็นสามส่วน - ขอ กลาง และท้าย ด้วยความเคารพของสตริงพาลินโดรมที่มีความยาวคี่พูดว่า 2n + 1 ที่นี่ 'ขอ' ประกอบด้วยอักขระ n ตัวแรกของสตริง 'กลาง' ประกอบด้วยอักขระ 1 ตัวเท่านั้นที่หมายถึง (n + 1) อักขระที่และ 'สิ้นสุด' ประกอบด้วย n อักขระสุดท้าย สตริงพาลินโดรม สำหรับสตริงพาลินโดรมที่มีความยาวเท่ากัน 2n จะมีช่องว่างใน 'กลาง' เสมอ เรารู้อยู่แล้วว่า 'สิ้นสุด' จะกลับกันจาก 'ขอ' ในแง่ของคำสั่งให้สตริงเป็นพาลินโดรม ตอนนี้ แนวคิดคือการนำการสังเกตข้างต้นไปใช้ในโซลูชันของเรา เนื่องจากอนุญาตให้สับเปลี่ยนอักขระได้ จึงไม่ต้องมีลำดับของอักขระในสตริงอินพุต ขั้นแรก เราได้รับความถี่ของอักขระแต่ละตัวในสตริงอินพุต หลังจากนั้นอักขระทั้งหมดที่มีแม้กระทั่ง (พูด 2n) ในสตริงอินพุตจะเป็นส่วนหนึ่งของสตริงเอาต์พุตเพราะเราสามารถตั้งค่าอักขระ n ตัวในสตริง 'ขอ' และอักขระ n ตัวอื่น ๆ ในสตริง 'สิ้นสุด' (ด้วยความช่วยเหลือของการรักษา ลำดับพาลินโดรม) สำหรับอักขระที่มีเหตุการณ์แปลก ๆ (เช่น 2n + 1) ในที่นี้ เราเติม "กลาง" ด้วยอักขระดังกล่าวทั้งหมด และอักขระ 2n ที่เหลือจะถูกแบ่งครึ่งและเพิ่มเมื่อเริ่มต้นและสิ้นสุด
ตัวอย่าง
// 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;
} ผลลัพธ์
pqrsrqp
