Minimize removals to remove another string as a subsequence of a given string | Function to print the minimum number of character removals required to remove X as a subsequence from the string str ; Length of the string str ; Length of the string X ; Stores the dp states ; Fill first row of dp [ ] [ ] ; If X [ j ] matches with str [ 0 ] ; If s [ i ] is equal to X [ j ] ; Update state after removing str [ i [ ; Update state after keeping str [ i ] ; If str [ i ] is not equal to X [ j ] ; Print the minimum number of characters removals ; Driver Code ; Input ; Function call to get minimum number of character removals
def printMinimumRemovals ( s , X ) : NEW_LINE INDENT N = len ( s ) NEW_LINE M = len ( X ) NEW_LINE dp = [ [ 0 for x in range ( M ) ] for y in range ( N ) ] NEW_LINE for j in range ( M ) : NEW_LINE INDENT if ( s [ 0 ] == X [ j ] ) : NEW_LINE INDENT dp [ 0 ] [ j ] = 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT if ( s [ i ] == X [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + 1 NEW_LINE if ( j != 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT print ( dp [ N - 1 ] [ M - 1 ] ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " btagd " NEW_LINE X = " bad " NEW_LINE printMinimumRemovals ( s , X ) NEW_LINE DEDENT