Minimize removal or insertions required to make two strings equal | Java 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
import java . io . * ; import java . util . * ; class GFG { static int findLongestSubstring ( int posA , int posB , String A , String B , int canSkip , int n , 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 . charAt ( posA ) == B . charAt ( posB ) ) { op1 = 1 + findLongestSubstring ( posA + 1 , posB + 1 , A , B , 0 , n , dp ) ; } if ( canSkip == 1 ) { 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 ) ) ; } static void minOperations ( String A , String B , int N ) { int [ ] [ ] [ ] dp = new int [ N ] [ N ] [ 2 ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } System . out . println ( N - findLongestSubstring ( 0 , 0 , A , B , 1 , N , dp ) ) ; } public static void main ( String [ ] args ) { String A = " abab " ; String B = " baba " ; int N = A . length ( ) ; minOperations ( A , B , N ) ; } }