ตรวจสอบว่า String ทำเป็น Palindrome ได้หรือไม่หลังลบสูงสุด k ตัวอักษรใน Python

ปัญหา: กำหนด String s และ k หาว่าสามารถลบ ≤ k ตัวอักษร ได้ Palindrome หรือไม่

Observation: ตัวอักษรที่ต้องลบขั้นต่ำ = |s| - LPS(s) โดย LPS = Longest Palindromic Subsequence = LCS(s, reverse(s))

อัลกอริทึม: LCS (Longest Common Subsequence)

1. คำนวณ LCS ระหว่าง s และ reverse(s) → ได้ LPS Length
2. Min Deletions = len(s) - LPS
3. ถ้า Min Deletions ≤ k → True

การติดตั้ง

class Solution:
    def solve(self, s, k):
        def lcs(a, b):
            m, n = len(a), len(b)
            # DP Table (m+1) x (n+1)
            dp = [[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]:
                        dp[i][j] = 1 + dp[i-1][j-1]
                    else:
                        dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            return dp[m][n]
        
        lps_length = lcs(s, s[::-1])
        min_deletions = len(s) - lps_length
        return min_deletions <= k

# Test
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))  # True (ลบ i,u,v,r → "level")

คำอธิบาย

• s[::-1] = Reverse ของ String

• lcs(s, s[::-1]) = LPS Length (Longest Palindromic Subsequence)

• ตัวอย่าง: "lieuvrel" ↔ "lervueil" → LCS = "level" (Length 5)

• Min Deletions = 8 - 5 = 3 ≤ 4 → True

Complexity

• Time: O(n²) где n = len(s)
• Space: O(n²) DP Table (สามารถลดเหลือ O(n) ได้ด้วย 2 Rows)

Space Optimized Version (O(n) Space)

def lcs_optimized(a, b):
    m, n = len(a), len(b)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[j-1]:
                curr[j] = 1 + prev[j-1]
            else:
                curr[j] = max(curr[j-1], prev[j])
        prev, curr = curr, prev  # Swap
    
    return prev[n]

Variations

# Return Min Deletions แทน Boolean
def min_deletions_to_palindrome(s):
    lps = lcs(s, s[::-1])
    return len(s) - lps

# Return Palindrome Itself (Reconstruction)
def build_palindrome(s):
    # ต้อง Trace Back DP Table
    ...

# k = 0: Check ถ้าเป็น Palindrome อยู่แล้ว
def is_palindrome(s):
    return s == s[::-1]

ตัวอย่างเพิ่มเติม