Given a binary string S, the task is to partition the sequence into K non-empty subsets such that the sum of products of occurrences of 0 and 1 for all subsets is minimum. If impossible print -1.
Examples:
Input: S = “0001”, K = 2
Output: 0
Explanation
We have 3 choices {0, 001}, {00, 01}, {000, 1}
The respective sum of products are {1*0 + 2*1 = 2}, {2*0 + 1*1 = 1}, {3*0 + 0*1 = 0}.
Input: S = “1011000110110100”, K = 5
Output: 8
Explanation: The subsets {10, 11, 000, 11011, 0100} minimizes the sum of product { 1*1 + 0*2 + 3*0 + 1*4 + 3*1 = 8 }.
Approach: In order to solve this problem we are using bottom-up dynamic programming.
- We calculate the minimum sum of products for all subsets and then, for every subset we use this value to compute the minimum sum of products for all sizes of that subset.
- For a subset starting at index i and ending at index j the value will be minimum of dp[i-1] + (count_zero * count_one) where count_zero and count_one are the occurrences of 0 and 1 between i and j respectively.
- For each index j, we find the minimum value amongst all possible values of i.
- Return dp[N – 1] for the final answer.
Below code is the implementation of the above approach:
C++
// C++ Program to split a given string// into K segments such that the sum// of product of occurrence of// characters in them is minimized#include <bits/stdc++.h>using namespace std;// Function to return the minimum// sum of products of occurrences// of 0 and 1 in each segmentsint minSumProd(string S, int K){ // Store the length of // the string int len = S.length(); // Not possible to // generate subsets // greater than the // length of string if (K > len) return -1; // If the number of subsets // equals the length if (K == len) return 0; vector<int> dp(len); int count_zero = 0, count_one = 0; // Precompute the sum of // products for all index for (int j = 0; j < len; j++) { (S[j] == '0') ? count_zero++ : count_one++; dp[j] = count_zero * count_one; } // Calculate the minimum sum of // products for K subsets for (int i = 1; i < K; i++) { for (int j = len; j >= i; j--) { count_zero = 0, count_one = 0; dp[j] = INT_MAX; for (int k = j; k >= i; k--) { (S[k] == '0') ? count_zero++ : count_one++; dp[j] = min( dp[j], count_zero * count_one + dp[k - 1]); } } } return dp[len - 1];}// Driver codeint main(){ string S = "1011000110110100"; int K = 5; cout << minSumProd(S, K) << '\n'; return 0;} |
Java
// Java Program to split a given String// into K segments such that the sum// of product of occurrence of// characters in them is minimizedimport java.util.*;class GFG{// Function to return the minimum// sum of products of occurrences// of 0 and 1 in each segmentsstatic int minSumProd(String S, int K){ // Store the length of // the String int len = S.length(); // Not possible to // generate subsets // greater than the // length of String if (K > len) return -1; // If the number of subsets // equals the length if (K == len) return 0; int []dp = new int[len]; int count_zero = 0, count_one = 0; // Precompute the sum of // products for all index for (int j = 0; j < len; j++) { if(S.charAt(j) == '0') count_zero++; else count_one++; dp[j] = count_zero * count_one; } // Calculate the minimum sum of // products for K subsets for (int i = 1; i < K; i++) { for (int j = len-1; j >= i; j--) { count_zero = 0; count_one = 0; dp[j] = Integer.MAX_VALUE; for (int k = j; k >= i; k--) { if(S.charAt(k) == '0') count_zero++; else count_one++; dp[j] = Math.min(dp[j], count_zero * count_one + dp[k - 1]); } } } return dp[len - 1];}// Driver codepublic static void main(String[] args){ String S = "1011000110110100"; int K = 5; System.out.print(minSumProd(S, K));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to split a given String# into K segments such that the sum# of product of occurrence of# characters in them is minimizedimport sys# Function to return the minimum# sum of products of occurrences# of 0 and 1 in each segmentsdef minSumProd(S, K): # Store the length of # the String Len = len(S); # Not possible to # generate subsets # greater than the # length of String if (K > Len): return -1; # If the number of subsets # equals the length if (K == Len): return 0; dp = [0] * Len; count_zero = 0; count_one = 0; # Precompute the sum of # products for all index for j in range(0, Len, 1): if (S[j] == '0'): count_zero += 1; else: count_one += 1; dp[j] = count_zero * count_one; # Calculate the minimum sum of # products for K subsets for i in range(1, K): for j in range(Len - 1, i - 1, -1): count_zero = 0; count_one = 0; dp[j] = sys.maxsize; for k in range(j, i - 1, -1): if (S[k] == '0'): count_zero += 1; else: count_one += 1; dp[j] = min(dp[j], count_zero * count_one + dp[k - 1]); return dp[Len - 1];# Driver codeif __name__ == '__main__': S = "1011000110110100"; K = 5; print(minSumProd(S, K));# This code is contributed by 29AjayKumar |
C#
// C# program to split a given String// into K segments such that the sum// of product of occurrence of// characters in them is minimizedusing System;class GFG{// Function to return the minimum// sum of products of occurrences// of 0 and 1 in each segmentsstatic int minSumProd(string S, int K){ // Store the length of // the String int len = S.Length; // Not possible to // generate subsets // greater than the // length of String if (K > len) return -1; // If the number of subsets // equals the length if (K == len) return 0; int []dp = new int[len]; int count_zero = 0, count_one = 0; // Precompute the sum of // products for all index for(int j = 0; j < len; j++) { if(S[j] == '0') { count_zero++; } else { count_one++; } dp[j] = count_zero * count_one; } // Calculate the minimum sum // of products for K subsets for(int i = 1; i < K; i++) { for(int j = len - 1; j >= i; j--) { count_zero = 0; count_one = 0; dp[j] = Int32.MaxValue; for(int k = j; k >= i; k--) { if(S[k] == '0') { count_zero++; } else { count_one++; } dp[j] = Math.Min(dp[j], count_zero * count_one + dp[k - 1]); } } } return dp[len - 1];}// Driver codepublic static void Main(string[] args){ string S = "1011000110110100"; int K = 5; Console.Write(minSumProd(S, K));}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript Program to split a given string// into K segments such that the sum// of product of occurrence of// characters in them is minimized// Function to return the minimum// sum of products of occurrences// of 0 and 1 in each segmentsfunction minSumProd(S, K) { // Store the length of // the string let len = S.length; // Not possible to // generate subsets // greater than the // length of string if (K > len) return -1; // If the number of subsets // equals the length if (K == len) return 0; let dp = new Array(len); let count_zero = 0, count_one = 0; // Precompute the sum of // products for all index for (let j = 0; j < len; j++) { (S[j] == '0') ? count_zero++ : count_one++; dp[j] = count_zero * count_one; } // Calculate the minimum sum of // products for K subsets 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] == '0') ? count_zero++ : count_one++; dp[j] = Math.min( dp[j], count_zero * count_one + dp[k - 1]); } } } return dp[len - 1];}// Driver codelet S = "1011000110110100";let K = 5;document.write(minSumProd(S, K));// This code is contributed by _saurabh_jaiswal</script> |
Output:
8
Time Complexity: O(K*N*N)
Auxiliary Space Complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
