पायथन में सबसे लंबे पैलिंड्रोमिक बाद की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक लोअरकेस स्ट्रिंग s है; हमें s में सबसे लंबे पैलिंड्रोमिक अनुक्रम की लंबाई ज्ञात करनी है।

इसलिए, यदि इनपुट s ="aolpeuvekyl" जैसा है, तो आउटपुट 5 होगा, क्योंकि पैलिंड्रोम "स्तर" है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=आकार का
• एक फ़ंक्शन को परिभाषित करें dp() । यह ले जाएगा मैं, जे
• यदि i, j के समान है, तो
  • वापसी 1
• अन्यथा जब i> j, तब
  • वापसी 0
• अन्यथा,
  • यदि s[i] s[j] के समान है, तो
    • रिटर्न 2 + डीपी(i + 1, j-1)
  • अन्यथा,
    • अधिकतम dp(i + 1, j) और dp(i, j-1) लौटाएं
• रिटर्न डीपी(0, एन -1)

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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