ধারণা
একটি প্রদত্ত স্ট্রিং এর সম্মানের সাথে, স্ট্রিং থেকে অক্ষর অপসারণ বা এলোমেলো করে তৈরি করা যেতে পারে এমন দীর্ঘতম প্যালিনড্রোম নির্ধারণ করুন। অবশেষে শুধুমাত্র একটি প্যালিনড্রোম ফেরত দিন যদি দেখা যায় যে দীর্ঘতম দৈর্ঘ্যের একাধিক প্যালিনড্রোম স্ট্রিং আছে।
ইনপুট
pqr
আউটপুট
p OR q OR r
ইনপুট
ppqqrr
আউটপুট
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
ইনপুট
pqp
আউটপুট
pqp
পদ্ধতি
এখানে, আমরা যেকোনো প্যালিনড্রোমিক স্ট্রিংকে তিনটি ভাগে বিভক্ত করতে পারি - বেগ, মিড এবং এন্ড। বিজোড় দৈর্ঘ্যের প্যালিন্ড্রোমিক স্ট্রিংকে 2n + 1 বলুন, এখানে 'বেগ' স্ট্রিংটির প্রথম n অক্ষর নিয়ে গঠিত, 'মিড' শুধুমাত্র 1টি অক্ষর নিয়ে গঠিত যার মানে (n + 1)তম অক্ষর এবং 'শেষ' শেষ অক্ষর নিয়ে গঠিত প্যালিনড্রোমিক স্ট্রিং জোড় দৈর্ঘ্য 2n এর প্যালিনড্রোমিক স্ট্রিং এর ক্ষেত্রে, 'মাঝে' সবসময় খালি থাকবে। আমরা ইতিমধ্যেই জানি যে স্ট্রিংকে প্যালিনড্রোম হওয়ার ক্রম অনুসারে 'শেষ' হবে 'বেগ'-এর বিপরীত। এখন ধারণাটি আমাদের সমাধানে উপরের পর্যবেক্ষণ বাস্তবায়ন করা। যেহেতু অক্ষরগুলিকে এলোমেলো করার অনুমতি দেওয়া হয়েছে, ইনপুট স্ট্রিংটিতে অক্ষরের ক্রম কোন ব্যাপার নেই৷ এখন আমরা প্রথমে ইনপুট স্ট্রিং-এর প্রতিটি অক্ষরের ফ্রিকোয়েন্সি পাই। এর পরে ইনপুট স্ট্রিং-এ যতগুলো অক্ষর আছে (বলুন 2n) সেগুলো আউটপুট স্ট্রিং-এর অংশ হবে কারণ আমরা সহজেই 'বেগ' স্ট্রিং-এ n অক্ষর এবং 'শেষ' স্ট্রিং-এ অন্যান্য 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
