কনসেপ্ট
একটি স্ট্রিং দেওয়া আছে। স্ট্রিং থেকে অক্ষর মুছে বা শাফল (shuffle) করে সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোম তৈরি করুন। একাধিক প্যালিনড্রোম থাকলে যেকোনো একটি ফেরত দিন।
ইনপুট ১
pqr
আউটপুট ১
p বা q বা r
ইনপুট ২
ppqqrr
আউটপুট ২
pqrrqp বা qprrpq বা rqppqr (দৈর্ঘ্য ৬)
ইনপুট ৩
pqp
আউটপুট ৩
pqp
পদ্ধতি
যেকোনো প্যালিনড্রোম তিন भागে ভাগ করা যায়: beg (শুরু), mid (মাঝ), end (শেষ)। বिषম দৈর্ঘ্যের প্যালিনড্রোমে mid-এ এক অক্ষর থাকে, জোড় দৈর্ঘ্যে mid খালি থাকে। end همیشه beg-এর রিভার্স।
শাফলিং অনুমতিত থাকায় ইনপুট স্ট্রিং-এর অক্ষরের ক্রম গুরুত্বপূর্ণ নয়। প্রতিটি অক্ষরের ফ্রিকোয়েন্সি গণনা করুন। জোড় ফ্রিকোয়েন্সি (২n) والے অক্ষরগুলো beg-এ n এবং end-এ n করে রাখা যায়। বिषম ফ্রিকোয়েন্সি (২n+1) वाले অক্ষরগুলো থেকে একটি mid-এ রাখুন, বাকি ২n টি beg ও end-এ বाँটুন।
উদাহরণ (C++ কোড)
// C++ প্রোগ্রাম: স্ট্রিং থেকে অক্ষর মুছে/শাফল করে সর্বোচ্চ প্যালিনড্রোম
#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]]++;
string beg1 = "", mid1 = "", end1 = "";
// ছোট হাতের অক্ষর ধরে নেওয়া হয়েছে, সহজে প্রসারিত করা যায়
for (char ch1 = 'a'; ch1 <= 'z'; ch1++) {
if (count1[ch1] & 1) { // বিষম ফ্রিকোয়েন্সি
mid1 = ch1; // mid একদম একটি অক্ষর ধারণ করবে
count1[ch1]--; // জোড় করে দিন
}
// জোড় ফ্রিকোয়েন্সি
for (int i = 0; i < count1[ch1] / 2; i++)
beg1.push_back(ch1);
}
end1 = beg1;
reverse(end1.begin(), end1.end());
return beg1 + mid1 + end1;
}
int main() {
string str1 = "pqqprrs";
cout << findLongestPalindrome(str1);
return 0;
}
আউটপুট
pqrsrqp
