Arrange a binary string to get maximum value within a range of indices | Python implementation of the approach ; Storing the count of 1 's in the string ; Query of l and r ; Applying range update technique . ; Taking prefix sum to get the range update values ; Final array which will store the arranged string ; if after maximizing the ranges any 1 is left then we maximize the string lexicographically . ; Driver Code
def arrange ( s ) : NEW_LINE INDENT cc = 0 NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if ( s [ i ] == "1" ) : NEW_LINE INDENT cc += 1 NEW_LINE DEDENT DEDENT a = [ 0 ] * ( len ( s ) + 1 ) NEW_LINE qq = [ ( 2 , 3 ) , ( 5 , 5 ) ] NEW_LINE n = len ( qq ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT l , r = qq [ i ] [ 0 ] , qq [ i ] [ 1 ] NEW_LINE l -= 1 NEW_LINE r -= 1 NEW_LINE a [ l ] += 1 NEW_LINE a [ r + 1 ] -= 1 NEW_LINE DEDENT for i in range ( 1 , len ( a ) ) : NEW_LINE INDENT a [ i ] = a [ i ] + a [ i - 1 ] NEW_LINE DEDENT zz = [ 0 ] * len ( s ) NEW_LINE for i in range ( len ( a ) - 1 ) : NEW_LINE INDENT if ( a [ i ] > 0 ) : NEW_LINE INDENT if ( cc > 0 ) : NEW_LINE INDENT zz [ i ] = 1 NEW_LINE cc -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( cc == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( cc > 0 ) : NEW_LINE INDENT for i in range ( len ( s ) ) : NEW_LINE INDENT if ( zz [ i ] == 0 ) : NEW_LINE INDENT zz [ i ] = 1 NEW_LINE cc -= 1 NEW_LINE DEDENT if ( cc == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT print ( * zz , sep = " " ) NEW_LINE DEDENT str = "11100" NEW_LINE arrange ( str ) NEW_LINE