Minimize removals to remove another string as a subsequence of a given string | Java program for the above approach ; 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 str [ 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void printMinimumRemovals ( String str , String X ) { int N = str . length ( ) ; int M = X . length ( ) ; int dp [ ] [ ] = new int [ N ] [ M ] ; for ( int j = 0 ; j < M ; j ++ ) { if ( str . charAt ( 0 ) == X . charAt ( j ) ) { dp [ 0 ] [ j ] = 1 ; } } for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { if ( str . charAt ( i ) == X . charAt ( j ) ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + 1 ; if ( j != 0 ) dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - 1 ] ) ; } else { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } } } System . out . println ( dp [ N - 1 ] [ M - 1 ] ) ; } public static void main ( String [ ] args ) { String str = " btagd " ; String X = " bad " ; printMinimumRemovals ( str , X ) ; } }