Minimize cost of swapping set bits with unset bits in a given Binary string | Javascript program for the above approach ; Function to find the minimum cost required to swap every set bit with an unset bit ; Stores the indices of set and unset bits of the string S ; Traverse the string S ; Store the indices ; Initialize a dp table of size n1 * n2 ; Set unreachable states to INF ; Fill the dp Table according to the given recurrence relation ; Update the value of dp [ i ] [ j ] ; Return the minimum cost ; Driver Code
let INF = 1000000000 ; function minimumCost ( s ) { let N = s . length ; let A = [ ] , B = [ ] ; for ( let i = 0 ; i < N ; i ++ ) { if ( s [ i ] == " " ) { A . push ( i ) ; } else { B . push ( i ) ; } } let n1 = A . length ; let n2 = B . length ; let dp = new Array ( n1 + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( n2 + 1 ) . fill ( 0 ) ) ; for ( let i = 1 ; i <= n1 ; i ++ ) { dp [ i ] [ 0 ] = INF ; } for ( let i = 1 ; i <= n1 ; i ++ ) { for ( let j = 1 ; j <= n2 ; j ++ ) { dp [ i ] [ j ] = Math . min ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j - 1 ] + Math . abs ( A [ i - 1 ] - B [ j - 1 ] ) ) ; } } return dp [ n1 ] [ n2 ] ; } let S = " " ; document . write ( minimumCost ( S ) ) ;