Python से सबसे लंबे पैलिंड्रोमिक सबसीक्वेंस की लंबाई कैसे ढूंढें?

डायनामिक प्रोग्रामिंग से ऐसा सबसे लंबा सम-लंबाई पैलिंड्रोमिक सबसीक्वेंस ढूंढें जिसमें मध्य को छोड़कर लगातार समान कैरेक्टर्स न हों।

एल्गोरिदम

• n = स्ट्रिंग लंबाई।
• dp = n×n 2D ऐरे जहां प्रत्येक सेल एक पेयर (length, char) स्टोर करता है।
• बॉटम-अप DP: i = n-1 से 0, j = i+1 से n-1 तक।
• अगर s[i] == s[j] और dp[i+1][j-1][1] != s[i], तो dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])।
• अन्यथा तीनों में से मैक्स लें: dp[i+1][j], dp[i][j-1], dp[i+1][j-1]।
• उत्तर dp[0][n-1][0]।

उदाहरण कोड

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'))  # आउटपुट: 4

इनपुट/आउटपुट

इनपुट: 'efeffe'
आउटपुट: 4 (सबसीक्वेंस 'effe')