Remove minimum characters from string to split it into three substrings under given constraints | Python 3 program for the above approach ; Function that counts minimum character that must be removed ; Length of string ; Create prefix array ; Initialize first position ; Fill prefix array ; Initialise maxi ; Check all the possibilities by putting i and j at different position & find maximum among them ; Print the characters to be removed ; Driver Code ; Given String ; Function Call
import sys NEW_LINE def min_remove ( st ) : NEW_LINE INDENT N = len ( st ) NEW_LINE prefix_a = [ 0 ] * ( N + 1 ) NEW_LINE prefix_b = [ 0 ] * ( N + 1 ) NEW_LINE prefix_c = [ 0 ] * ( N + 1 ) NEW_LINE prefix_a [ 0 ] = 0 NEW_LINE prefix_b [ 0 ] = 0 NEW_LINE prefix_c [ 0 ] = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( st [ i - 1 ] == ' a ' ) : NEW_LINE INDENT prefix_a [ i ] = ( prefix_a [ i - 1 ] + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT prefix_a [ i ] = prefix_a [ i - 1 ] NEW_LINE DEDENT if ( st [ i - 1 ] == ' b ' ) : NEW_LINE INDENT prefix_b [ i ] = ( prefix_b [ i - 1 ] + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT prefix_b [ i ] = prefix_b [ i - 1 ] NEW_LINE DEDENT if ( st [ i - 1 ] == ' c ' ) : NEW_LINE INDENT prefix_c [ i ] = ( prefix_c [ i - 1 ] + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT prefix_c [ i ] = prefix_c [ i - 1 ] NEW_LINE DEDENT DEDENT maxi = - sys . maxsize - 1 ; NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT for j in range ( i , N + 1 ) : NEW_LINE INDENT maxi = max ( maxi , ( prefix_a [ i ] + ( prefix_b [ j ] - prefix_b [ i ] ) + ( prefix_c [ N ] - prefix_c [ j ] ) ) ) NEW_LINE DEDENT DEDENT print ( ( N - maxi ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " aaaabaaxccac " NEW_LINE min_remove ( st ) NEW_LINE DEDENT