Split a binary string into K subsets minimizing sum of products of occurrences of 0 and 1 | Python3 program to split a given String into K segments such that the sum of product of occurence of characters in them is minimized ; Function to return the minimum sum of products of occurences of 0 and 1 in each segments ; Store the length of the String ; Not possible to generate subsets greater than the length of String ; If the number of subsets equals the length ; Precompute the sum of products for all index ; Calculate the minimum sum of products for K subsets ; Driver code
import sys NEW_LINE def minSumProd ( S , K ) : NEW_LINE INDENT Len = len ( S ) ; NEW_LINE if ( K > Len ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT if ( K == Len ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT dp = [ 0 ] * Len ; NEW_LINE count_zero = 0 ; NEW_LINE count_one = 0 ; NEW_LINE for j in range ( 0 , Len , 1 ) : NEW_LINE INDENT if ( S [ j ] == '0' ) : NEW_LINE INDENT count_zero += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT count_one += 1 ; NEW_LINE DEDENT dp [ j ] = count_zero * count_one ; NEW_LINE DEDENT for i in range ( 1 , K ) : NEW_LINE INDENT for j in range ( Len - 1 , i - 1 , - 1 ) : NEW_LINE INDENT count_zero = 0 ; NEW_LINE count_one = 0 ; NEW_LINE dp [ j ] = sys . maxsize ; NEW_LINE for k in range ( j , i - 1 , - 1 ) : NEW_LINE INDENT if ( S [ k ] == '0' ) : NEW_LINE INDENT count_zero += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT count_one += 1 ; NEW_LINE DEDENT dp [ j ] = min ( dp [ j ] , count_zero * count_one + dp [ k - 1 ] ) ; NEW_LINE DEDENT DEDENT DEDENT return dp [ Len - 1 ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = "1011000110110100" ; NEW_LINE K = 5 ; NEW_LINE print ( minSumProd ( S , K ) ) ; NEW_LINE DEDENT