Split a binary string into K subsets minimizing sum of products of occurrences of 0 and 1 | 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
function minSumProd ( S , K ) { let len = S . length ; if ( K > len ) return - 1 ; if ( K == len ) return 0 ; let dp = new Array ( len ) ; let count_zero = 0 , count_one = 0 ; for ( let j = 0 ; j < len ; j ++ ) { ( S [ j ] == ' ' ) ? count_zero ++ : count_one ++ ; dp [ j ] = count_zero * count_one ; } for ( let i = 1 ; i < K ; i ++ ) { for ( let j = len ; j >= i ; j -- ) { count_zero = 0 , count_one = 0 ; dp [ j ] = Number . MAX_SAFE_INTEGER ; for ( let k = j ; k >= i ; k -- ) { ( S [ k ] == ' ' ) ? count_zero ++ : count_one ++ ; dp [ j ] = Math . min ( dp [ j ] , count_zero * count_one + dp [ k - 1 ] ) ; } } } return dp [ len - 1 ] ; } let S = " " ; let K = 5 ; document . write ( minSumProd ( S , K ) ) ;