এই সমস্যায়, n আকারের একটি স্ট্রিং দেওয়া থাকে। এবং স্ট্রিংয়ের ক্যারেক্টার ব্যবহার করে যেসব প্যালিনড্রোমিক পারমুটেশন তৈরি করা সম্ভব সেগুলো অ্যালফাবেটিক্যাল অর্ডারে প্রিন্ট করতে হবে। যদি স্ট্রিং দিয়ে প্যালিনড্রোম তৈরি করা না যায় তবে '-1' প্রিন্ট করুন।
উদাহরণ দিয়ে বুঝি:
ইনপুট: string = “abcba” আউটপুট: abcba bacba
এখন, এটি সমাধান করার জন্য আমাদের সব সম্ভাব্য প্যালিনড্রোম খুঁজে বের করতে হবে এবং সেগুলো অ্যালফাবেটিক্যাল অর্ডারে (লেক্সিকোগ্রাফিক্যাল অর্ডারে) সাজাতে হবে। অথবা আরেকটি পদ্ধতি হতে পারে স্ট্রিং থেকে তৈরি লেক্সিকোগ্রাফিক্যালি প্রথম প্যালিনড্রোম খুঁজে বের করা। তারপর সিকোয়েন্সের পরের প্যালিনড্রোম খুঁজে বের করা।
এই জন্য, আমরা নিচের ধাপগুলো করব:
ধাপ ১ − স্ট্রিংয়ের সব ক্যারেক্টার এর ফ্রিকোয়েন্সি স্টোর করুন।
ধাপ ২ − এখন চেক করুন স্ট্রিং প্যালিনড্রোম बना পারে কিনা। যদি না পারায় "No palindrome can be formed" প্রিন্ট করে এক্সিট করুন। অন্যথায় করুন:
ধাপ ৩ − লজিক অনুযায়ী একটি স্ট্রিং তৈরি করুন যে সব ক্যারেক্টার যাদের জোড় ঘটনা সেগুলো এক স্ট্রিং তৈরি করবে এবং বিজোড় ঘটনা যাদের সেগুলো অন্য স্ট্রিং। এবং বিজোড় স্ট্রিংকে জোড় স্ট্রিংয়ের মাঝপথে রাখব (অর্থাৎ even_string + odd_string + even_string ফর্মে)।
এটি ব্যবহার করে আমরা লেক্সিকোগ্রাফিক্যালি প্রথম প্যালিনড্রোম খুঁজে পাব। তারপর কনসেকিউটিভ লেক্সিকোগ্রাফিক্যাল কম্বিনেশন চেক করে পরেরটি খুঁজে বের করব।
C++ উদাহরণ
#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
