সমস্যা বিবরণ
আকার 'n'-এর একটি স্ট্রিং দেওয়া আছে। স্ট্রিংটিকে প্যালিনড্রোম করার জন্য ন্যূনতম কতগুলো ক্যারেক্টার ডিলিট করতে হবে তা বের করতে হবে।
যদি দেওয়া স্ট্রিং "abcda" হয়, তবে প্রথম এবং শেষ ছাড়া যেকোনো ২টি ক্যারেক্টার ডিলিট করলে প্যালিনড্রোম হবে।
- 'b' এবং 'c' ডিলিট করলে "ada" প্যালিনড্রোম
- 'c' এবং 'd' ডিলিট করলে "aba" প্যালিনড্রোম
- 'b' এবং 'd' ডিলিট করলে "aca" প্যালিনড্রোম
এলগরিদম
1. দিয়ো স্ট্রিংয়ের লংগেস্ট প্যালিনড্রোমিক সাবসিকোয়েন্স (LPS) বের করুন। এটাকে 'lpsSize' বলুন। 2. ডিলিট করার ন্যূনতম ক্যারেক্টার = (স্ট্রিং দৈর্ঘ্য - lpsSize)
উদাহরণ কোড
#include <iostream>
#include <algorithm>
using namespace std;
int lps(string s, int i, int j) {
if (i == j) {
return 1;
}
if (s[i] == s[j] && i + 1 == j) {
return 2;
}
if (s[i] == s[j]) {
return lps(s, i + 1, j - 1) + 2;
}
return max(lps(s, i, j - 1), lps(s, i + 1, j));
}
int minDeletion(string s) {
int n = s.size();
int lpsSize = lps(s, 0, n);
return (n - lpsSize);
}
int main() {
cout << "Minimum characters to be deleted = " << minDeletion("abcda") << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum characters to be deleted = 2
