इस समस्या में, हमें आकार n की एक स्ट्रिंग दी गई है। और हमें स्ट्रिंग के वर्णों का उपयोग करके उत्पन्न होने वाले सभी संभावित पैलिंड्रोमिक क्रमपरिवर्तन को वर्णमाला क्रम में प्रिंट करना है। यदि स्ट्रिंग का उपयोग करके पैलिंड्रोम नहीं बनाया जा सकता तो '-1' प्रिंट करें।
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
इनपुट: स्ट्रिंग = "abcba" आउटपुट: abcba bacba
अब, इसे हल करने के लिए हमें स्ट्रिंग से बने सभी पैलिंड्रोम ढूंढने होंगे और फिर उन्हें वर्णमाला क्रम (लेक्सिकोग्राफिकल क्रम) में व्यवस्थित करना होगा। या दूसरा तरीका स्ट्रिंग से बने लेक्सिकोग्राफिकली पहले पैलिंड्रोम को ढूंढना हो सकता है। फिर अनुक्रम के क्रमिक अगले पैलिंड्रोम को ढूंढें।
इसके लिए, हम निम्नलिखित चरण करेंगे -
चरण 1 - स्ट्रिंग के सभी वर्णों की घटना की आवृत्ति संग्रहीत करें।
चरण 2 - अब जांचें कि क्या स्ट्रिंग पैलिंड्रोम बना सकती है। यदि नहीं तो "कोई पैलिंड्रोम नहीं बनाया जा सकता" प्रिंट करें और बाहर निकलें। अन्यथा करें -
चरण 3 - तर्क के आधार पर एक स्ट्रिंग बनाएं कि सम घटना वाले सभी वर्ण एक स्ट्रिंग बनाते हैं और विषम घटना वाले अन्य से। और हम विषम स्ट्रिंग को सम स्ट्रिंग के बीच सैंडविच करेंगे (यानी सम_स्ट्रिंग + विषम_स्ट्रिंग + सम_स्ट्रिंग के रूप में)।
इसका उपयोग करके हम लेक्सिकोग्राफिकली पहला पैलिंड्रोम ढूंढ सकते हैं। फिर समवर्ती लेक्सिकोग्राफिकल संयोजनों की जांच करके अगला ढूंढें।
उदाहरण
अवधारणा को चित्रित करने के लिए प्रोग्राम -
#include <iostream> #include <string.h> using namespace std; const char MAX_CHAR = 26; void countFreq(char str[], int freq[], int n){ for (int i = 0; i < n; i++) freq[str[i] - 'a']++; } bool canMakePalindrome(int freq[], int n){ int count_odd = 0; for (int i = 0; i < 26; i++) if (freq[i] % 2 != 0) count_odd++; if (n % 2 == 0) { if (count_odd > 0) return false; else return true; } if (count_odd != 1) return false; return true; } bool isPalimdrome(char str[], int n){ int freq[26] = { 0 }; countFreq(str, freq, n); if (!canMakePalindrome(freq, n)) return false; char odd_char; for (int i = 0; i < 26; i++) { if (freq[i] % 2 != 0) { freq[i]--; odd_char = (char)(i + 'a'); break; } } int front_index = 0, rear_index = n - 1; for (int i = 0; i < 26; i++) { if (freq[i] != 0) { char ch = (char)(i + 'a'); for (int j = 1; j <= freq[i] / 2; j++) { str[front_index++] = ch; str[rear_index--] = ch; } } } if (front_index == rear_index) str[front_index] = odd_char; return true; } void reverse(char str[], int i, int j){ while (i < j) { swap(str[i], str[j]); i++; j--; } } bool nextPalindrome(char str[], int n){ if (n <= 3) return false; int mid = n / 2 - 1; int i, j; for (i = mid - 1; i >= 0; i--) if (str[i] < str[i + 1]) break; if (i < 0) return false; int smallest = i + 1; for (j = i + 2; j <= mid; j++) if (str[j] > str[i] && str[j] < str[smallest]) smallest = j; swap(str[i], str[smallest]); swap(str[n - i - 1], str[n - smallest - 1]); reverse(str, i + 1, mid); if (n % 2 == 0) reverse(str, mid + 1, n - i - 2); else reverse(str, mid + 2, n - i - 2); return true; } void printAllPalindromes(char str[], int n){ if (!(isPalimdrome(str, n))) { cout<<"-1"; return; } do { cout<<str<<endl; } while (nextPalindrome(str, n)); } int main(){ char str[] = "abccba"; int n = strlen(str); cout<<"The list of palindromes possible is :\n"; printAllPalindromes(str, n); return 0; } आउटपुट
संभावित पैलिंड्रोम की सूची है -
abccba acbbca baccab bcaacb cabbac cbaabc
