determining if a string is a k-palindrome by not only removing first and last characters

Question

I was just writing a program to determine if a given string is a palindrome when at most n letters are removed from it. I came up with a program in python which works but only by removing the first or last characters of the string recursively. It does not remove/ check what happens when you remove characters which are not on one of the ends. I was wondering how I could improve my program so that it does check all possibilities. This is my code so far:

def palindromecheck(s,n):
    #print(s)
    #print(n)

    if (len(s)) <=1:
        return True
    if n==0:
        return False
    
    while s[0] == s[(len(s)-1)]:
        s=s[1:-1]
        if len(s) <= 1:
            return True


    
    return palindromecheck((s[:-1]),(n-1)) or palindromecheck((s[1:]),(n-1))

Answer 1

This is a typical DP problem. You could try to use DP (memo() helper funtion to save the repetitions). The idea is to find the longest palindromic subsequence of the given string. Then |lps - original string| <= k, conclude that the string is k-palindrome.

def checkPalindrome(s: str, k: int) -> bool:
    # memo to save the repeatition
    memo = {}
 
    def helper(start, end):
        if start >= end: return 0           # <= 1 char is a palindrome
          
        if (start, end) in memo:
            return memo[(start, end)]

        if s[start] == s[end]:
            result = helper(start + 1, end - 1)
        else:
            result = 1 + min(helper(start + 1, end), \
                             helper(start, end - 1))

        memo[(start, end)] = result
        return result

    return helper(0, len(s) - 1) <= k

Alternatively, you can use lru_chache for the intermediate results:

from functools import lru_cache
from typing import List


def checkPalindrome(w: str, k: int) -> bool:
    @lru_cache(maxsize=None)
    
    def helper(s, e):            
        if s > e: return 0
        
        if w[s] != w[e]:
            return 1 + min(helper(s+1, e), \
                           helper(s, e-1))
        else:
            return helper(s+1, e-1)
        
    return helper(0, len(w)-1) <= k


w = "asparagus"
k = 4

print(checkPalindrome(w, k))