Find if string is K | Find if given string is K - Palindrome or not ; Create a table to store results of subproblems ; Fill dp [ ] [ ] in bottom up manner ; If first string is empty , only option is to remove all characters of second string ; If second string is empty , only option is to remove all characters of first string ; If last characters are same , ignore last character and recur for remaining string ; If last character are different , remove it and find minimum ; dp [ i ] [ j ] = 1 + min ( dp [ i - 1 ] [ j ] , Remove from str1 ( dp [ i ] [ j - 1 ] ) ) Remove from str2 ; Returns true if str is k palindrome . ; Driver program
def isKPalDP ( str1 , str2 , m , n ) : NEW_LINE INDENT dp = [ [ 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 : NEW_LINE elif not j : NEW_LINE elif ( str1 [ i - 1 ] == str2 [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE DEDENT DEDENT return dp [ m ] [ n ] NEW_LINE DEDENT def isKPal ( string , k ) : NEW_LINE INDENT revStr = string [ : : - 1 ] NEW_LINE l = len ( string ) NEW_LINE return ( isKPalDP ( string , revStr , l , l ) <= k * 2 ) NEW_LINE DEDENT string = " acdcb " NEW_LINE k = 2 NEW_LINE print ( " Yes " if isKPal ( string , k ) else " No " ) NEW_LINE