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

একটি ছোট হাতের স্ট্রিং s দেওয়া আছে। আমাদের স্ট্রিং-এसे এমন একটি সাবসিকোয়েন্স (সাবসিকোয়েন্স মানে উপাদানগুলো ক্রম ধরে থাকবে কিন্তু একে অপরের সাথে 붙어 থাকতে হবে না) খুঁজে বের করতে হবে যা প্যালিনড্রোম এবং দৈর্ঘ্য সর্বোচ্চ।

উদাহরণস্বরূপ, s = "aolpeuvekyl" হলে আউটপুট ৫, কারণ "level" একটি প্যালিনড্রোমিক সাবসিকোয়েন্স।

সমাধানের পদ্ধতি (রিকার্সিভ DP / 탑-ডাউন)

1. n = len(s)।
2. dp(i, j) ফাংশন ডিফাইন করুন যা সাবস্ট্রিং s[i..j]-এ সর্বোচ্চ প্যালিনড্রোমিক সাবসিকোয়েন্সের দৈর্ঘ্য রিটার্ন করে।
   • বেস কেস: i == j হলে ১ রিটার্ন করুন (একক ক্যারেক্টার প্যালিনড্রোম)।
   • i > j হলে ০ রিটার্ন করুন।
   • যদি s[i] == s[j], তবে return 2 + dp(i+1, j-1)।
   • অন্যথায়, return max(dp(i+1, j), dp(i, j-1))।
3. dp(0, n-1) কল করে ফলাফল পান।

নোট: এটি টপ-ডাউন রিকার্সিভ DP। বটম-আপ DP বা LCS-বেজড সমাধানও সম্ভব।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, s):
        n = len(s)
        def dp(i, j):
            if i == j:
                return 1
            elif i > j:
                return 0
            else:
                if s[i] == s[j]:
                    return 2 + dp(i + 1, j - 1)
                else:
                    return max(dp(i + 1, j), dp(i, j - 1))
        return dp(0, n - 1)

ob = Solution()
s = "aolpeuvekyl"
print(ob.solve(s))

ইনপুট

"aolpeuvekyl"

আউটপুট

5