अवधारणा
एक दी गई स्ट्रिंग के संबंध में, उस सबसे लंबे पैलिंड्रोम को निर्धारित करें जिसे स्ट्रिंग से वर्णों को हटाकर या फेरबदल करके बनाया जा सकता है। अंत में केवल एक पैलिंड्रोम लौटाएं यदि यह देखा गया है कि सबसे लंबी लंबाई के कई पैलिंड्रोम स्ट्रिंग्स हैं।
इनपुट
pqr
आउटपुट
p OR q OR r
इनपुट
ppqqrr
आउटपुट
pqrrqp OR qprrpq OR rqppqr OR लंबाई 6 का कोई अन्य पैलिंड्रोमिक स्ट्रिंग।
इनपुट
pqp
आउटपुट
pqp
विधि
यहां, हम किसी भी पैलिंड्रोमिक स्ट्रिंग को तीन भागों में विभाजित कर सकते हैं – beg, mid और end। विषम लंबाई के पैलिंड्रोमिक स्ट्रिंग के संबंध में मान लें 2n + 1, यहां 'beg' में स्ट्रिंग के पहले n वर्ण होते हैं, 'mid' में केवल 1 वर्ण होता है यानी (n + 1)वां वर्ण और 'end' में पैलिंड्रोमिक स्ट्रिंग के अंतिम n वर्ण होते हैं। सम लंबाई 2n के पैलिंड्रोमिक स्ट्रिंग के संबंध में, 'mid' में हमेशा खाली होगा। हम पहले से जानते हैं कि स्ट्रिंग के पैलिंड्रोम होने के लिए क्रम के संबंध में 'end', 'beg' का उल्टा होगा। अब अवधारणा हमारे समाधान में उपरोक्त अवलोकन को लागू करना है। क्योंकि वर्णों का फेरबदल अनुमत है, इनपुट स्ट्रिंग में वर्णों के क्रम की कोई बात नहीं है। अब हम पहले इनपुट स्ट्रिंग में प्रत्येक वर्ण की आवृत्ति प्राप्त करते हैं। उसके बाद इनपुट स्ट्रिंग में सम घटना वाले सभी वर्ण (मान लें 2n) आउटपुट स्ट्रिंग का हिस्सा होंगे क्योंकि हम आसानी से n वर्णों को 'beg' स्ट्रिंग में सेट कर सकते हैं और अन्य n वर्ण 'end' स्ट्रिंग में बनाएंगे (पैलिंड्रोमिक क्रम को बनाए रखने में मदद से)। विषम घटना वाले वर्णों (मान लें 2n + 1) के संबंध में, यहां, हम 'mid' को ऐसे सभी वर्णों में से एक से भरते हैं और शेष 2n वर्णों को आधे में विभाजित करते हैं और शुरुआत और अंत में जोड़ते हैं।
उदाहरण
// C++ program to find the longest palindrome by removing // or shuffling characters from the given string #include <bits/stdc++.h> using namespace std; // दी गई स्ट्रिंग से वर्णों को हटाकर या फेरबदल करके सबसे लंबा पैलिंड्रोम खोजने वाला फ़ंक्शन string findLongestPalindrome(string str1){ // एक स्ट्रिंग में वर्णों की आवृत्ति संग्रहीत करने के लिए इंगित किया जाता है int count1[256] = { 0 }; // इनपुट स्ट्रिंग में वर्णों की आवृत्ति निर्धारित करें for (int i = 0; i < str1.size(); i++) count1[str1[i]]++; // कोई भी पैलिंड्रोमिक स्ट्रिंग जिसमें तीन भाग होते हैं // beg1 + mid1 + end1 string beg1 = "", mid1 = "", end1 = ""; //यह समाधान मानता है कि स्ट्रिंग में केवल लोअरकेस वर्ण हैं // मौजूद हैं। हम इसे आसानी से बढ़ा सकते हैं // वर्णों के किसी भी सेट पर विचार करने के लिए for (char ch1 = 'a'; ch1 <= 'z'; ch1++){ // अब यदि वर्तमान वर्ण की आवृत्ति विषम है if (count1[ch1] & 1){ // यहां mid1 में केवल 1 वर्ण होगा। यह // अगले वर्ण के साथ ओवरराइड हो जाएगा // जिसकी विषम आवृत्ति है mid1 = ch1; // वर्ण की आवृत्ति को घटाकर // इसे सम बनाएं और वर्तमान वर्ण को // फिर से विचार करें count1[ch1--]--; } // यहां यदि वर्तमान वर्ण की आवृत्ति सम है else{ // अब यदि गिनती n (एक सम संख्या) है, तो पुश करें // n/2 वर्णों को beg स्ट्रिंग में और शेष // n/2 वर्ण end स्ट्रिंग का हिस्सा बनेंगे for (int i = 0; i < count1[ch1]/2 ; i++) beg1.push_back(ch1); } } // यहां end, beg का उल्टा होगा end1 = beg1; reverse(end1.begin(), end1.end()); // अब पैलिंड्रोम स्ट्रिंग लौटाएं return beg1 + mid1 + end1; } // ड्राइवर कोड int main(){ string str1 = "pqqprrs"; cout << findLongestPalindrome(str1); return 0; }आउटपुट
pqrsrqp
