अवधारणा
किसी दिए गए स्ट्रिंग के संबंध में, सबसे लंबा पैलिंड्रोम निर्धारित करें जो स्ट्रिंग से वर्णों को हटाकर या फेरबदल करके बनाया जा सकता है। अंत में केवल एक पैलिंड्रोम लौटाएं यदि यह देखा गया है कि सबसे लंबी लंबाई के कई पैलिंड्रोम तार हैं।
इनपुट
pqr
आउटपुट
p OR q OR r
इनपुट
ppqqrr
आउटपुट
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
इनपुट
pqp
आउटपुट
pqp
विधि
यहां, हम किसी भी पैलिंड्रोमिक स्ट्रिंग को तीन भागों में विभाजित कर सकते हैं - भीख, मध्य और अंत। विषम लंबाई जैसे 2n + 1 के पैलिंड्रोमिक स्ट्रिंग के संबंध में, यहाँ 'beg' में स्ट्रिंग के पहले n वर्ण होते हैं, 'मध्य' में केवल 1 वर्ण होता है जिसका अर्थ है (n + 1)वाँ वर्ण और 'अंत' में अंतिम n वर्ण होते हैं पैलिंड्रोमिक स्ट्रिंग। 2n लंबाई के पैलिंड्रोमिक स्ट्रिंग के संबंध में, 'मध्य' में हमेशा खाली रहेगा। हम पहले से ही जानते हैं कि स्ट्रिंग के पैलिंड्रोम होने के क्रम के संबंध में 'अंत' 'भीख' के विपरीत होगा। अब अवधारणा हमारे समाधान में उपरोक्त अवलोकन को लागू करने की है। क्योंकि वर्णों के फेरबदल की अनुमति है, इनपुट स्ट्रिंग में वर्णों के क्रम की कोई बात नहीं है। अब हम पहले इनपुट स्ट्रिंग में प्रत्येक वर्ण की आवृत्ति प्राप्त करते हैं। उसके बाद इनपुट स्ट्रिंग में सम घटना (जैसे 2n) वाले सभी वर्ण आउटपुट स्ट्रिंग का हिस्सा होंगे क्योंकि हम आसानी से n वर्णों को 'beg' स्ट्रिंग में और अन्य 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