Length of longest substring to be deleted to make a string equal to another string | Java program to implement the above approach ; Function to print the length of longest substring to be deleted ; Stores the length of string ; Store the position of previous matched character of str1 ; Store the position of first occurrence of str2 in str1 ; Find the position of the first occurrence of str2 ; Store the index of str1 ; If both characters not matched ; Store the length of the longest deleted substring ; Store the position of last occurrence of str2 in str1 ; If both characters not matched ; Update res ; Update res . ; Driver Code ; Given string ; Function call
import java . io . * ; class GFG { static int longDelSub ( String str1 , String str2 ) { int N = str1 . length ( ) ; int M = str2 . length ( ) ; int prev_pos = 0 ; int pos [ ] = new int [ M ] ; for ( int i = 0 ; i < M ; i ++ ) { int index = prev_pos ; while ( index < N && str1 . charAt ( index ) != str2 . charAt ( i ) ) { index ++ ; } pos [ i ] = index ; prev_pos = index + 1 ; } int res = N - prev_pos ; prev_pos = N - 1 ; for ( int i = M - 1 ; i >= 0 ; i -- ) { int index = prev_pos ; while ( index >= 0 && str1 . charAt ( index ) != str2 . charAt ( i ) ) { index -- ; } if ( i != 0 ) { res = Math . max ( res , index - pos [ i - 1 ] - 1 ) ; } prev_pos = index - 1 ; } res = Math . max ( res , prev_pos + 1 ) ; return res ; } public static void main ( String [ ] args ) { String str1 = " GeeksforGeeks " ; String str2 = " forks " ; System . out . print ( longDelSub ( str1 , str2 ) ) ; } }