Length of longest substring to be deleted to make a string equal to another string | Function to prthe 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 . ; Given string ; Function call
def longDelSub ( str1 , str2 ) : NEW_LINE INDENT N = len ( str1 ) NEW_LINE M = len ( str2 ) NEW_LINE prev_pos = 0 NEW_LINE pos = [ 0 ] * M NEW_LINE for i in range ( M ) : NEW_LINE INDENT index = prev_pos NEW_LINE while ( index < N and str1 [ index ] != str2 [ i ] ) : NEW_LINE INDENT index += 1 NEW_LINE DEDENT pos [ i ] = index NEW_LINE prev_pos = index + 1 NEW_LINE DEDENT res = N - prev_pos NEW_LINE prev_pos = N - 1 NEW_LINE for i in range ( M - 1 , - 1 , - 1 ) : NEW_LINE INDENT index = prev_pos NEW_LINE while ( index >= 0 and str1 [ index ] != str2 [ i ] ) : NEW_LINE INDENT index -= 1 NEW_LINE DEDENT if ( i != 0 ) : NEW_LINE INDENT res = max ( res , index - pos [ i - 1 ] - 1 ) NEW_LINE DEDENT prev_pos = index - 1 NEW_LINE DEDENT res = max ( res , prev_pos + 1 ) NEW_LINE return res NEW_LINE DEDENT str1 = " GeeksforGeeks " NEW_LINE str2 = " forks " NEW_LINE print ( longDelSub ( str1 , str2 ) ) NEW_LINE