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

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

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

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम रिकर्सिव DP (डायनामिक प्रोग्रामिंग) का उपयोग करेंगे:

• n := s का आकार
• dp(i, j) फंक्शन परिभाषित करें:
  • यदि i == j है, तो 1 लौटाएं
  • अन्यथा यदि i > j है, तो 0 लौटाएं
  • अन्यथा:
    • यदि s[i] == s[j] है, तो 2 + dp(i + 1, j - 1) लौटाएं
    • अन्यथा, max(dp(i + 1, j), dp(i, j - 1)) लौटाएं
• dp(0, n - 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