Arrange a binary string to get maximum value within a range of indices | Java 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
class GFG { static void arrange ( String s ) { int cc = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s . charAt ( i ) == '1' ) cc ++ ; } int [ ] a = new int [ s . length ( ) + 1 ] ; int qq [ ] [ ] = { { 2 , 3 } , { 5 , 5 } } ; int n = qq . length ; for ( int i = 0 ; i < n ; i ++ ) { int l = qq [ i ] [ 0 ] , r = qq [ i ] [ 1 ] ; l -- ; r -- ; a [ l ] ++ ; a [ r + 1 ] -- ; } int len_a = a . length ; for ( int i = 1 ; i < len_a ; i ++ ) { a [ i ] += a [ i - 1 ] ; } int [ ] zz = new int [ s . length ( ) ] ; for ( int 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 ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( zz [ i ] == 0 ) { zz [ i ] = 1 ; cc -- ; } if ( cc == 0 ) break ; } } for ( int i = 0 ; i < s . length ( ) ; i ++ ) System . out . print ( zz [ i ] ) ; System . out . println ( ) ; } public static void main ( String [ ] args ) { String str = "11100" ; arrange ( str ) ; } }