Chương trình tìm độ dài dãy con palindrome dài nhất bằng Python

Cho một chuỗi. Cần tìm dãy con palindrome có độ dài chẵn và không chứa hai ký tự liên tiếp giống nhau (trừ ở giữa). Trả về độ dài dãy con đó.

Ví dụ: s = 'efeffe' → kết quả 4 (dãy 'effe').

Thuật toán

• n := độ dài s
• dp := mảng 2D n×n, mỗi phần tử là cặp (0, chuỗi rỗng)
• Duyệt i từ n-1 xuống 0, j từ i+1 đến n-1:
  • Nếu s[i] == s[j] và chuỗi trong dp[i+1][j-1] khác s[i]: dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
  • Ngược lại: dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) theo phần tử đầu của cặp
• Trả về phần tử đầu của dp[0][n-1]

Code Python

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'))

Input

'efeffe'

Output

4