সমস্যা বিবরণ
একটি স্ট্রিং দেওয়া আছে। কাজ হলো স্ট্রিংয়ের সাব-স্ট্রিং এর সর্বোচ্চ দৈর্ঘ্য বের করা যেটিকে প্যালিনড্রোম হিসেবে সাজানো যায়।
উদাহরণ
ইনপুট স্ট্রিং = “5432112356” হলে উত্তর হবে ৬ কারণ সর্বোচ্চ প্যালিনড্রোম সাব-স্ট্রিং হলো “321123” এবং এর দৈর্ঘ্য ৬।
অ্যালগরিদম
- যদি সাব-স্ট্রিংর দৈর্ঘ্য বিজোড় হয়, তবে সেটিকে চূড়ান্ত সমাধানে বিবেচনা করা যাবে না।
- যদি সাব-স্ট্রিংর দৈর্ঘ্য জোড় হয়, তবে সেটি একটি সম্ভাব্য সমাধান হতে পারে শুধু তখন যখন সাব-স্ট্রিংর প্রতিটি ক্যারেক্টর জোড়বার আবির্ভূত হয়, যা ডিকশনারি কাউন্ট দিয়ে করা যায়। আমরা যাচাই করি প্রতিটি ক্যারেক্টর জোড়বার আবির্ভূত হয় কিনা। যদি হয়, তবে সেটিকে সম্ভাব্য সমাধানের মধ্যে অন্তর্ভুক্ত করি। তারপর স্ট্রিংয়ের পরবর্তী ক্যারেক্টরটি অন্তর্ভুক্ত করে পরবর্তী সাব-স্ট্রিং তৈরি করি যা সিম্পলি end বাড়িয়ে এবং রিকার্সিভলি যাচাই করি বড় দৈর্ঘ্যের সাব-স্ট্রিং তৈরি করা যায় কিনা যেটি শর্তগুলো পূরণ করে এবং সকল সম্ভাব্য সমাধানের মধ্যে সর্বোচ্চটি রিটার্ন করি।
উদাহরণ
#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
