C++ তে দীর্ঘতম প্যালিনড্রোমিক সাবক্যুয়েন্স

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদেরকে s-এ দীর্ঘতম প্যালিনড্রোমিক পরবর্তী দৈর্ঘ্য খুঁজে বের করতে হবে। আমরা অনুমান করতে পারি যে s-এর সর্বোচ্চ দৈর্ঘ্য হল 1000৷ তাই যদি ইনপুটটি "bbbab" এর মতো হয়, তাহলে আউটপুট হবে 4৷ একটি সম্ভাব্য প্যালিনড্রোমিক অনুসারী হল "bbbb"৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

x :=s, তারপর বিপরীত x, n :=s এর আকার
যদি n 0 হয়, তাহলে 0 ফেরত দিন
s এর আগে একটি ফাঁকা স্থান যোগ করে s আপডেট করুন এবং x এর আগে একটি ফাঁকা স্থান যোগ করে x আপডেট করুন
ret :=0
একটি ম্যাট্রিক্স ডিপি আকারের (n + 1) x (n + 1) করুন
আমি 1 থেকে n
রিটার্ন 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"