Minimize cost of swapping set bits with unset bits in a given Binary string | Python 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
INF = 1000000000 ; NEW_LINE def minimumCost ( s ) : NEW_LINE INDENT N = len ( s ) ; NEW_LINE A = [ ] NEW_LINE B = [ ] NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT if ( s [ i ] == "1" ) : NEW_LINE A . append ( i ) ; NEW_LINE else : NEW_LINE B . append ( i ) ; NEW_LINE DEDENT n1 = len ( A ) NEW_LINE n2 = len ( B ) NEW_LINE dp = [ [ 0 for i in range ( n2 + 1 ) ] for j in range ( n1 + 1 ) ] NEW_LINE for i in range ( 1 , n1 + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = INF NEW_LINE DEDENT for i in range ( 1 , n1 + 1 ) : NEW_LINE INDENT for j in range ( 1 , n2 + 1 ) : NEW_LINE dp [ i ] [ j ] = min ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j - 1 ] + abs ( A [ i - 1 ] - B [ j - 1 ] ) ) ; NEW_LINE DEDENT return dp [ n1 ] [ n2 ] ; NEW_LINE DEDENT S = "1010001" ; NEW_LINE print ( minimumCost ( S ) ) ; NEW_LINE