Minimize removal or insertions required to make two strings equal | Function to find the longest substring in string A which is a subsequence in B ; If the indices are out of bounds ; If an already computed subproblem occurred ; Required answer if the all the characters of A and B are the same ; Required answer if there is no substring A which is a subsequence in B ; Required answer if the current character in B is skipped ; The answer for the subproblem is the maximum among the three ; Function to return the minimum strings operations required to make two strings equal ; Initialize the dp vector ; Driver Code
function findLongestSubstring ( posA , posB , A , B , canSkip , n , dp ) { if ( posA >= n posB >= n ) { return 0 ; } if ( dp [ posA ] [ posB ] [ canSkip ] != - 1 ) { return dp [ posA ] [ posB ] [ canSkip ] ; } var op1 = 0 ; var op2 = 0 ; var op3 = 0 ; if ( A [ posA ] == B [ posB ] ) { op1 = 1 + findLongestSubstring ( posA + 1 , posB + 1 , A , B , 0 , n , dp ) ; } if ( canSkip ) { op2 = findLongestSubstring ( posA + 1 , posB , A , B , canSkip , n , dp ) ; } op3 = findLongestSubstring ( posA , posB + 1 , A , B , canSkip , n , dp ) ; return dp [ posA ] [ posB ] [ canSkip ] = Math . max ( op1 , Math . max ( op2 , op3 ) ) ; } function minOperations ( A , B , N ) { var dp = Array . from ( Array ( N ) , ( ) => Array ( N ) ) ; for ( var i = 0 ; i < N ; i ++ ) for ( var j = 0 ; j < N ; j ++ ) dp [ i ] [ j ] = new Array ( 2 ) . fill ( - 1 ) ; document . write ( N - findLongestSubstring ( 0 , 0 , A , B , 1 , N , dp ) ) ; } var A = " " ; var B = " " ; var N = A . length ; minOperations ( A , B , N ) ;