Arrange a binary string to get maximum value within a range of indices | Javascript 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
function arrange ( s ) { var cc = 0 ; for ( var i = 0 ; i < s . length ; i ++ ) { if ( s [ i ] == ' ' ) cc ++ ; } var a = Array ( s . length + 1 ) . fill ( 0 ) ; var qq = [ [ 2 , 3 ] , [ 5 , 5 ] ] ; var n = qq . length ; for ( var i = 0 ; i < n ; i ++ ) { var l = qq [ i ] [ 0 ] , r = qq [ i ] [ 1 ] ; l -- , r -- ; a [ l ] ++ ; a [ r + 1 ] -- ; } var len_a = a . length ; for ( var i = 1 ; i < len_a ; i ++ ) { a [ i ] += a [ i - 1 ] ; } var zz = Array ( s . length ) . fill ( 0 ) ; for ( var i = 0 ; i < len_a - 1 ; i ++ ) { if ( a [ i ] > 0 ) { if ( cc > 0 ) { zz [ i ] = 1 ; cc -- ; } else break ; } if ( cc == 0 ) break ; } if ( cc > 0 ) { for ( var i = 0 ; i < s . length ; i ++ ) { if ( zz [ i ] == 0 ) { zz [ i ] = 1 ; cc -- ; } if ( cc == 0 ) break ; } } for ( var i = 0 ; i < s . length ; i ++ ) document . write ( zz [ i ] ) ; document . write ( " " ) ; } var str = " " ; arrange ( str ) ;