পাইথন ব্যবহার করে দীর্ঘতম প্যালিনড্রোমিক পরবর্তী দৈর্ঘ্য খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন, আমাদের একটি স্ট্রিং দেওয়া হয়েছে। আমাদের এমন একটি প্যালিনড্রোমিক অনুবর্তন খুঁজে বের করতে হবে যা সমান দৈর্ঘ্যের এবং মাঝখানে ছাড়া পরপর দুটি একই অক্ষর থাকে না। আমাদের আউটপুট হিসাবে এই ধরনের সাবস্ট্রিংগুলির দৈর্ঘ্য ফেরত দিতে হবে।

সুতরাং, যদি ইনপুট s ='efeffe' এর মত হয়, তাহলে আউটপুট হবে 4

আউটপুট হল 4 কারণ শুধুমাত্র একটি প্যালিনড্রোমিক অনুবর্তন রয়েছে যা সমান দৈর্ঘ্যের। স্ট্রিং হল 'effe' যার দৈর্ঘ্য 4।

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

n :=s এর আকার
dp :=one n x n 2d অ্যারে যেখানে প্রতিটি আইটেম একটি জোড়া আকারে (0, ফাঁকা স্ট্রিং)
n-1 থেকে -1 রেঞ্জে i এর জন্য, 1 দ্বারা হ্রাস করুন, করুন
- i+1 থেকে n রেঞ্জের মধ্যে j এর জন্য, করুন
  - যদি s[i] s[j] এর মত হয় এবং dp[i+1, j-1] এর স্ট্রিং s[i] না হয়, তাহলে
    - dp[i, j] :=একটি জোড়া তৈরি করুন (dp[i+1, j-1] + 2, s[i] এর প্রথম উপাদান)
  - অন্যথায়,
    - dp[i, j] :=(dp[i+1, j], dp[i, j-1], dp[i+1,j-1]) এর মধ্যে নির্বাচন করুন যার জন্য জোড়ার প্রথম উপাদান সর্বাধিক হয়
  - dp[0, n-1]
    এ সংরক্ষিত জোড়ার প্রথম উপাদান ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

def solve(s):
   n = len(s)
   dp = [[(0, '')]*n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(i+1, n):
         if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
            dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
         else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
   return dp[0][n-1][0]
print(solve('efeffe'))

ইনপুট

'efeffe'