Find if string is K | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; L [ m ] [ n ] contains length of LCS for X and Y ; find if given string is K - Palindrome or not ; Find reverse of string ; find longest palindromic subsequence of given string ; If the difference between longest palindromic subsequence and the original string is less than equal to k , then the string is k - palindrome ;  ; Driver program
def lcs ( X , Y , m , n ) : NEW_LINE INDENT L = [ [ 0 ] * ( n + 1 ) for _ in range ( m + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if not i or not j : NEW_LINE INDENT L [ i ] [ j ] = 0 NEW_LINE DEDENT elif X [ i - 1 ] == Y [ j - 1 ] : NEW_LINE INDENT L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return L [ m ] [ n ] NEW_LINE DEDENT def isKPal ( string , k ) : NEW_LINE INDENT n = len ( string ) NEW_LINE revStr = string [ : : - 1 ] NEW_LINE lps = lcs ( string , revStr , n , n ) NEW_LINE return ( n - lps <= k ) NEW_LINE DEDENT / * Swap values of left and right * / NEW_LINE string = " abcdeca " NEW_LINE k = 2 NEW_LINE print ( " Yes " if isKPal ( string , k ) else " No " ) NEW_LINE