সমস্যা বিবরণ
একটি স্ট্রিং s দেওয়া থাকলে, যেকোনো পজিশনে ক্যারেক্টার ইন্সার্ট করে সেটিকে প্যালিনড্রোম বানাতে হবে। ন্যূনতম কতটি ইন্সারশন লাগবে তা বের করতে হবে।
উদাহরণ
s = "mad" → আউটপুট = 2 (পূর্বে "da" যোগ করলে "damad" বা পরে "am" যোগ করলে "madam")
সমাধান পদ্ধতি
- LCS (Longest Common Subsequence) ব্যবহার করা হয়।
- স্ট্রিং s এবং এর রিভার্স x-এর LCS বের করা হয়।
- উত্তর = s.length() - LCS(s, reverse(s))।
- DP টেবিল দিয়ে LCS গণনা করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
int lcs(string s) {
string x = s;
int n = s.size();
reverse(x.begin(), x.end());
s = " " + s;
x = " " + x;
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (s[i] == x[j])
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
}
}
return dp[n][n];
}
public:
int minInsertions(string s) {
return s.size() - lcs(s);
}
};
int main() {
Solution ob;
cout << ob.minInsertions("mad");
return 0;
}ইনপুট ও আউটপুট
ইনপুট: "mad"
আউটপুট: 2
