Minimum steps to delete a string after repeated deletion of palindrome substrings | method returns minimum step for deleting the string , where in one step a palindrome is removed ; declare dp array and initialize it with 0 s ; loop for substring length we are considering ; loop with two variables i and j , denoting starting and ending of substrings ; If substring length is 1 , then 1 step will be needed ; delete the ith char individually and assign result for subproblem ( i + 1 , j ) ; if current and next char are same , choose min from current and subproblem ( i + 2 , j ) ; loop over all right characters and suppose Kth char is same as ith character then choose minimum from current and two substring after ignoring ith and Kth char ; Uncomment below snippet to print actual dp tablex for ( int i = 0 ; i < N ; i ++ , cout << endl ) for ( int j = 0 ; j < N ; j ++ ) cout << dp [ i ] [ j ] << " ▁ " ; ; Driver Code
def minStepToDeleteString ( str ) : NEW_LINE INDENT N = len ( str ) NEW_LINE dp = [ [ 0 for x in range ( N + 1 ) ] for y in range ( N + 1 ) ] NEW_LINE for l in range ( 1 , N + 1 ) : NEW_LINE INDENT i = 0 NEW_LINE j = l - 1 NEW_LINE while j < N : NEW_LINE INDENT if ( l == 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 + dp [ i + 1 ] [ j ] NEW_LINE if ( str [ i ] == str [ i + 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( 1 + dp [ i + 2 ] [ j ] , dp [ i ] [ j ] ) NEW_LINE DEDENT for K in range ( i + 2 , j + 1 ) : NEW_LINE INDENT if ( str [ i ] == str [ K ] ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i + 1 ] [ K - 1 ] + dp [ K + 1 ] [ j ] , dp [ i ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT i += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT return dp [ 0 ] [ N - 1 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = "2553432" NEW_LINE print ( minStepToDeleteString ( str ) ) NEW_LINE DEDENT