সমস্যা বিবরণ
শুধু ইন্টিজার ক্যারেক্টার ধারণকারী একটি স্ট্রিং দেওয়া আছে। আমাদের এই স্ট্রিংয়ের সব ক্যারেক্টার ন্যূনতম ধাপে ডিলিট করতে হবে, যেখানে এক ধাপে একটি প্যালিনড্রোম সাবস্ট্রিং ডিলিট করা যায়। সাবস্ট্রিং ডিলিট করার পর বাকি অংশগুলো কনক্যাটিনেট হয়।
উদাহরণ
ইনপুট স্ট্রিং "3441213" হলে ন্যূনতম ২ ধাপ দরকার:
- প্রথমে স্ট্রিং থেকে "121" মুছে ফেলুন। বাকি স্ট্রিং: "3443"
- বাকি স্ট্রিং মুছে ফেলুন কারণ এটি প্যালিনড্রোম
অ্যালগরিদম
এই সমস্যা সমাধানের জন্য ডাইনামিক প্রোগ্রামিং ব্যবহার করা যায়।
1. dp[i][j] = সাবস্ট্রিং s[i, j] ডিলিট করতে কত ধাপ লাগবে। 2. প্রতিটি ক্যারেক্টার একা বা কোনো সাবস্ট্রিংয়ের অংশ হিসেবে ডিলিট হবে। প্রথম কেসে ক্যারেক্টারটি নিজে ডিলিট করে সাবপ্রব্লেম (i+1, j) কল করুন। 3. দ্বিতীয় কেসে করেন্ট ক্যারেক্টারের ডানপাশে থাকা সব occurrence চেক করুন। যদি K হয় একটা ইনডেক্স, তবে সমস্যা দুটি সাবপ্রব্লেমে বँটবে: (i+1, K-1) এবং (K+1, j)। 4. আমরা (i+1, K-1) সাবপ্রব্লেমে পৌঁছাতে পারি কারণ একই ক্যারেক্টার ডিলিট করে মিড সাবস্ট্রিং কল করা যায়। 5. একটা কেস হ্যান্ডেল করতে হবে যখন প্রথম দুটি ক্যারেক্টার একই হয়, সেক্ষেত্রে সরাসরি (i+2, j) সাবপ্রব্লেমে যাওয়া যায়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
int n = str.length();
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
}
}
for (int len = 1; len <= n; len++) {
for (int i = 0, j = len - 1; j < n; i++, j++) {
if (len == 1)
dp[i][j] = 1;
else {
dp[i][j] = 1 + dp[i + 1][j];
if (str[i] == str[i + 1]) {
dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
}
for (int K = i + 2; K <= j; K++){
if (str[i] == str[K]) {
dp[i][j] = min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
}
}
}
}
}
return dp[0][n - 1];
}
int main() {
string str = "3441213";
cout << "Minimum required steps: " << getMinRequiredSteps(str) << endl;
return 0;
}
উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে
আউটপুট
Minimum required steps: 2
