C++-এ সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোমিক সাবসিকোয়েন্স

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের s-এ সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোমিক সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে হবে। আমরা ধরে নিতে পারি s-এর সর্বোচ্চ দৈর্ঘ্য 1000। তাই যদি ইনপুট হয় “bbbab”, তবে আউটপুট হবে ৪। একটি সম্ভাব্য প্যালিনড্রোমিক সাবসিকোয়েন্স হল “bbbb”।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −

x := s, তারপর x উল্টান, n := s-এর আকার
যদি n ০ হয়, তবে ০ ফেরত দিন
s আপডেট করুন একটি ব্ল্যাঙ্ক স্পেস যোগ করে s-এর আগে, এবং x আপডেট করুন একটি ব্ল্যাঙ্ক স্পেস যোগ করে x-এর আগে
ret := ০
(n + 1) x (n + 1) আকারের একটি dp ম্যাট্রিক্স তৈরি করুন
i = 1 থেকে n পর্যন্ত
- j = 1 থেকে n পর্যন্ত
  - dp[i, j] := dp[i, j – 1], dp[i – 1, j]-এর max
  - যদি x[i] = s[j], তবে dp[i, j] := dp[i, j] এবং 1 + dp[i – 1, j – 1]-এর max
dp[n, n] ফেরত দিন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int longestPalindromeSubseq(string s) {       string x = s;       reverse(x.begin(), x.end());       int n = s.size();       if(!n) return 0;       s = " " + s;       x = " " + x;       int ret = 0;       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][j - 1], dp[i - 1][j]);             if(x[i] == s[j]) {                dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);             }          }       }       return dp[n][n];    } }; main(){    Solution ob;    cout << (ob.longestPalindromeSubseq("bbbab")); }

ইনপুট

"bbbab"