Chương trình kiểm tra có thể tạo palindrome sau khi xóa tối đa k ký tự trong Python

Cho chuỗi s, kiểm tra có thể làm thành palindrome sau khi xóa tối đa k ký tự không.

Ví dụ: s = "lieuvrel", k = 4 → True (xóa 3 ký tự thành "level").

Ý tưởng: Độ dài palindrome dài nhất = LCS (Longest Common Subsequence) giữa s và reverse(s). Số ký tự cần xóa = len(s) - LCS. Nếu ≤ k → True.

Thuật toán LCS (Dynamic Programming):

• Tạo bảng table[m+1][n+1] khởi tạo 0
• Duyệt i=1..m, j=1..n:
  • Nếu a[i-1] == b[j-1]: table[i][j] = 1 + table[i-1][j-1]
  • Ngược lại: table[i][j] = max(table[i][j-1], table[i-1][j])
• Trả về table[m][n]

Triển khai

class Solution:
    def solve(self, s, k):
        def lcs(a, b):
            m, n = len(a), len(b)
            table = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if a[i - 1] == b[j - 1]:
                        table[i][j] = 1 + table[i - 1][j - 1]
                    else:
                        table[i][j] = max(table[i][j - 1], table[i - 1][j])
            return table[m][n]
        
        return len(s) - lcs(s, s[::-1]) <= k

ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

Đầu vào

"lieuvrel", 4

Đầu ra

True

Phân tích: LCS("lieuvrel", "lervueil") = 5 ("level"). Cần xóa 8-5=3 ký tự ≤ 4 → True. Phức tạp O(n²) thời gian và không gian. Có thể tối ưu không gian xuống O(n) vì chỉ cần hàng trước.