Optimally accommodate 0 s and 1 s from a Binary String into K buckets | Function to find the minimum required sum using dynamic programming ; dp [ i ] [ j ] = minimum val of accommodation till j 'th index of the string  using i+1 number of buckets.  Final ans will be in dp[n-1][K-1] ; Corner cases ; Filling first row , if only 1 bucket then simple count number of zeros and ones and do the multiplication ; If k = 0 then this arrangement is not possible ; If no arrangement is possible then our answer will remain INT_MAX so return - 1 ; Driver code ; K buckets
function solve ( str , K ) { let n = str . length ; let dp = new Array ( K ) ; for ( let i = 0 ; i < K ; i ++ ) { dp [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = 0 ; } } if ( n < K ) return - 1 ; else if ( n == K ) return 0 ; let zeroes = 0 , ones = 0 ; for ( let i = 0 ; i < n ; i ++ ) { if ( str [ i ] == ' ' ) zeroes ++ ; else ones ++ ; dp [ 0 ] [ i ] = ones * zeroes ; } for ( let s = 1 ; s < K ; s ++ ) { for ( let i = 0 ; i < n ; i ++ ) { dp [ s ] [ i ] = Number . MAX_VALUE ; ones = 0 ; zeroes = 0 ; for ( let k = i ; k >= 0 ; k -- ) { if ( str [ k ] == ' ' ) zeroes ++ ; else ones ++ ; dp [ s ] [ i ] = Math . min ( dp [ s ] [ i ] , + ( ( k - 1 >= 0 ) ? ones * zeroes + dp [ s - 1 ] [ k - 1 ] : Number . MAX_VALUE ) ) ; } } } return ( dp [ K - 1 ] [ n - 1 ] == Number . MAX_VALUE ) ? - 1 : dp [ K - 1 ] [ n - 1 ] ; } let S = " " ; let K = 2 ; document . write ( solve ( S , K ) ) ;