Minimum steps to delete a string by deleting substring comprising of same characters | Function to return the minimum number of delete operations ; When a single character is deleted ; When a group of consecutive characters are deleted if any of them matches ; When both the characters are same then delete the letters in between them ; Memoize ; Driver code
def findMinimumDeletion ( l , r , dp , s ) : NEW_LINE INDENT if l > r : NEW_LINE INDENT return 0 NEW_LINE DEDENT if l == r : NEW_LINE INDENT return 1 NEW_LINE DEDENT if dp [ l ] [ r ] != - 1 : NEW_LINE INDENT return dp [ l ] [ r ] NEW_LINE DEDENT res = 1 + findMinimumDeletion ( l + 1 , r , dp , s ) NEW_LINE for i in range ( l + 1 , r + 1 ) : NEW_LINE INDENT if s [ l ] == s [ i ] : NEW_LINE INDENT res = min ( res , findMinimumDeletion ( l + 1 , i - 1 , dp , s ) + findMinimumDeletion ( i , r , dp , s ) ) NEW_LINE DEDENT DEDENT dp [ l ] [ r ] = res NEW_LINE return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abcddcba " NEW_LINE n = len ( s ) NEW_LINE N = 10 NEW_LINE dp = [ [ - 1 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE print ( findMinimumDeletion ( 0 , n - 1 , dp , s ) ) NEW_LINE DEDENT