Minimize removal or insertions required to make two strings equal | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findLongestSubstring ( int posA , int posB , string & A , string & B , bool canSkip , int n , vector < vector < vector < int > > > & dp ) { if ( posA >= n posB >= n ) { return 0 ; } if ( dp [ posA ] [ posB ] [ canSkip ] != -1 ) { return dp [ posA ] [ posB ] [ canSkip ] ; } int op1 = 0 ; int op2 = 0 ; int 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 ] = max ( op1 , max ( op2 , op3 ) ) ; } void minOperations ( string A , string B , int N ) { vector < vector < vector < int > > > dp ( N , vector < vector < int > > ( N , vector < int > ( 2 , -1 ) ) ) ; cout << N - findLongestSubstring ( 0 , 0 , A , B , 1 , N , dp ) ; } int main ( ) { string A = " abab " ; string B = " baba " ; int N = A . size ( ) ; minOperations ( A , B , N ) ; return 0 ; }