Minimum flips required to keep all 1 s together in a Binary string | Javascript implementation for Minimum number of flips required in a binary string such that all the 1 aTMs are together ; Length of the binary string ; Initial state of the dp dp [ 0 ] [ 0 ] will be 1 if the current bit is 1 and we have to flip it ; Initial state of the dp dp [ 0 ] [ 1 ] will be 1 if the current bit is 0 and we have to flip it ; dp [ i ] [ 0 ] = Flips required to make all previous bits zero Flip required to make current bit zero ; dp [ i ] [ 1 ] = minimum flips required to make all previous states 0 or make previous states 1 satisfying the condition ; Minimum of answer and flips required to make all bits 0 ; Driver code
function minFlip ( a ) { let n = a . length ; let dp = new Array ( n + 2 ) . fill ( 0 ) . map ( ( t ) => new Array ( 2 ) . fill ( 0 ) ) if ( a . charAt ( 0 ) == ' ' ) { dp [ 0 ] [ 0 ] = 1 ; } else dp [ 0 ] [ 0 ] = 0 ; if ( a . charAt ( 0 ) == ' ' ) dp [ 0 ] [ 1 ] = 1 ; else dp [ 0 ] [ 1 ] = 0 ; for ( let i = 1 ; i < n ; i ++ ) { if ( a . charAt ( i ) == ' ' ) { dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + 1 ; } else dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] ; if ( a . charAt ( i ) == ' ' ) { dp [ i ] [ 1 ] = Math . min ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] ) + 1 ; } else dp [ i ] [ 1 ] = Math . min ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] ) ; } let answer = Number . MAX_SAFE_INTEGER ; for ( let i = 0 ; i < n ; i ++ ) { answer = Math . min ( answer , dp [ i ] [ 1 ] + dp [ n - 1 ] [ 0 ] - dp [ i ] [ 0 ] ) ; } return Math . min ( answer , dp [ n - 1 ] [ 0 ] ) ; } let s = " " ; document . write ( minFlip ( s ) ) ;