সমস্যা বিবৃতি
একটি স্ট্রিং দেওয়া কাজটি হল সাব-স্ট্রিংটির সর্বাধিক দৈর্ঘ্য খুঁজে বের করা যা একটি প্যালিনড্রোমে সাজানো যেতে পারে।
উদাহরণ
যদি ইনপুট স্ট্রিং ="5432112356" তাহলে উত্তর হল 6 কারণ সর্বাধিক প্যালিনড্রোম সাবস্ট্রিং হল "321123" এবং এর দৈর্ঘ্য হল 6
অ্যালগরিদম
- যদি সাব-স্ট্রিংটির দৈর্ঘ্য বিজোড় হয়, তাহলে চূড়ান্ত সমাধানে এটি বিবেচনা করা যাবে না।
- যদি সাব-স্ট্রিং-এর দৈর্ঘ্য জোড় হয়, তবে এটি একটি সম্ভাব্য সমাধান হতে পারে যদি সেই সাব-স্ট্রিং-এর প্রতিটি অক্ষর সমান সংখ্যায় ঘটে যা অভিধান গণনা ব্যবহার করে করা যেতে পারে। আমরা পরীক্ষা করি যে প্রতিটি অক্ষর সমান সংখ্যায় ঘটে কিনা বা না। যদি হ্যাঁ, তাহলে আমরা এটিকে সম্ভাব্য সমাধানগুলির মধ্যে একটি হিসাবে অন্তর্ভুক্ত করি৷ তারপরে আমরা স্ট্রিংটিতে পরবর্তী অক্ষর অন্তর্ভুক্ত করে পরবর্তী সাব-স্ট্রিং তৈরি করি যা কেবলমাত্র শেষ বৃদ্ধির মাধ্যমে করা যেতে পারে এবং পুনরাবৃত্তিমূলকভাবে পরীক্ষা করে দেখুন যে আরও বেশি দৈর্ঘ্যের একটি সাব-স্ট্রিং তৈরি করা যেতে পারে যা প্রদত্ত শর্তগুলিকে সন্তুষ্ট করে এবং যথাসম্ভব সর্বোচ্চ ফেরত দেয়। সমাধান
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> countt;
bool isPalindromePossible(unordered_map<int, int> &countt) {
for (auto key : countt) {
if (key.second & 1) {
return false;
}
return true;
}
int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) {
if (end == str.length()) {
if ((end - start) % 2 == 0)
if (isPalindromePossible(countt))
return end - start;
return 0;
} else {
if ((end - start) % 2 == 0) {
if (isPalindromePossible(countt)) {
countt[str[end]]++;
return max(end - start, getMaxPalindrome(str, countt, start, end + 1));
} else {
countt[str[end]]++;
return getMaxPalindrome(str, countt, start, end + 1);
}
} else {
countt[str[end]]++;
unordered_map<int, int>
c(countt.begin(), countt.end());
int length = getMaxPalindrome(str, c, start, end + 1);
countt[str[end]]--;
countt[str[start]]--;
return max(length, getMaxPalindrome(str, countt, start + 1, end));
}
}
}
int main(int argc, char const *argv[]) {
string str = "5432112356";
int start = 0, end = 0;
cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMaximum palindrome length = 6
