Given a binary string str and an integer K, the task is to find the minimum cost required to partition the string into exactly K segments when the cost of each segment is the product of the number of set bits with the number of unset bits and total cost is sum of cost of all the individual segments.
Examples:
Input: str = “110101”, K = 3
Output: 2
11|0|101 is one of the possible partitions
where the cost is 0 + 0 + 2 = 2
Input: str = “1000000”, K = 5
Output: 0
Approach: Write a function minCost(s, k, cost, i, n) where cost is the minimum cost so far, i is the starting index for the partition and k is the remaining segments to be partitioned. Now, starting from the ith index calculate the cost of the current partition and call the same function recursively for the remaining substring. To memoize the result, a dp[][] array will be used where dp[i][j] will store the minimum cost of partitioning the string into j parts starting at the ith index.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 1001;// dp[i][j] will store the minimum cost// of partitioning the string into j// parts starting at the ith indexint dp[MAX][MAX];// Recursive function to find// the minimum cost requiredint minCost(string& s, int k, int cost, int i, int& n){ // If the state has been solved before if (dp[i][k] != -1) return dp[i][k]; // If only 1 part is left then the // remaining part of the string will // be considered as that part if (k == 1) { // To store the count of 0s and the // total characters of the string int count_0 = 0, total = n - i; // Count the 0s while (i < n) if (s[i++] == '0') count_0++; // Memoize and return the updated cost dp[i][k] = cost + (count_0 * (total - count_0)); return dp[i][k]; } int curr_cost = INT_MAX; int count_0 = 0; // Check all the positions to // make the current partition for (int j = i; j < n - k + 1; j++) { // Count the numbers of 0s if (s[j] == '0') count_0++; int curr_part_length = j - i + 1; // Cost of partition is equal to // (no. of 0s) * (no. of 1s) int part_cost = (count_0 * (curr_part_length - count_0)); // string, partitions, curr cost, // start index, length part_cost += minCost(s, k - 1, 0, j + 1, n); // Update the current cost curr_cost = min(curr_cost, part_cost); } // Memoize and return the updated cost dp[i][k] = (cost + curr_cost); return (cost + curr_cost);}// Driver codeint main(){ string s = "110101"; int n = s.length(); int k = 3; // Initialise the dp array for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) dp[i][j] = -1; } // string, partitions, curr cost, // start index, length cout << minCost(s, k, 0, 0, n); return 0;} |
Java
// Java implementation of the approach class GFG { final static int MAX = 1001; // dp[i][j] will store the minimum cost // of partitioning the string into j // parts starting at the ith index static int dp[][] = new int [MAX][MAX]; // Recursive function to find // the minimum cost required static int minCost(String s, int k, int cost, int i, int n) { // If the state has been solved before if (dp[i][k] != -1) return dp[i][k]; // If only 1 part is left then the // remaining part of the string will // be considered as that part if (k == 1) { // To store the count of 0s and the // total characters of the string int count_0 = 0, total = n - i; // Count the 0s while (i < n) if (s.charAt(i++) == '0') count_0++; // Memoize and return the updated cost dp[i][k] = cost + (count_0 * (total - count_0)); return dp[i][k]; } int curr_cost = Integer.MAX_VALUE; int count_0 = 0; // Check all the positions to // make the current partition for (int j = i; j < n - k + 1; j++) { // Count the numbers of 0s if (s.charAt(j) == '0') count_0++; int curr_part_length = j - i + 1; // Cost of partition is equal to // (no. of 0s) * (no. of 1s) int part_cost = (count_0 * (curr_part_length - count_0)); // string, partitions, curr cost, // start index, length part_cost += minCost(s, k - 1, 0, j + 1, n); // Update the current cost curr_cost = Math.min(curr_cost, part_cost); } // Memoize and return the updated cost dp[i][k] = (cost + curr_cost); return (cost + curr_cost); } // Driver code public static void main (String[] args) { String s = "110101"; int n = s.length(); int k = 3; // Initialise the dp array for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) dp[i][j] = -1; } // string, partitions, curr cost, // start index, length System.out.println(minCost(s, k, 0, 0, n)); } }// This code is contributed by AnkitRai01 |
Python 3
# Python 3 implementation of the approachimport sysMAX = 1001# dp[i][j] will store the minimum cost# of partitioning the string into j# parts starting at the ith indexdp = [[0 for i in range(MAX)] for j in range(MAX)]# Recursive function to find# the minimum cost requireddef minCost(s, k, cost, i, n): # If the state has been solved before if (dp[i][k] != -1): return dp[i][k] # If only 1 part is left then the # remaining part of the string will # be considered as that part if (k == 1): # To store the count of 0s and the # total characters of the string count_0 = 0 total = n - i # Count the 0s while (i < n): if (s[i] == '0'): count_0 += 1 i += 1 # Memoize and return the updated cost dp[i][k] = cost + (count_0 * (total - count_0)) return dp[i][k] curr_cost = sys.maxsize count_0 = 0 # Check all the positions to # make the current partition for j in range(i, n - k + 1, 1): # Count the numbers of 0s if (s[j] == '0'): count_0 += 1 curr_part_length = j - i + 1 # Cost of partition is equal to # (no. of 0s) * (no. of 1s) part_cost = (count_0 * (curr_part_length - count_0)) # string, partitions, curr cost, # start index, length part_cost += minCost(s, k - 1, 0, j + 1, n) # Update the current cost curr_cost = min(curr_cost, part_cost) # Memoize and return the updated cost dp[i][k] = (cost + curr_cost) return (cost + curr_cost)# Driver codeif __name__ == '__main__': s = "110101" n = len(s) k = 3 # Initialise the dp array for i in range(MAX): for j in range(MAX): dp[i][j] = -1 # string, partitions, curr cost, # start index, length print(minCost(s, k, 0, 0, n)) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG{ readonly static int MAX = 1001; // dp[i,j] will store the minimum cost // of partitioning the string into j // parts starting at the ith index static int [,]dp = new int [MAX, MAX]; // Recursive function to find // the minimum cost required static int minCost(String s, int k, int cost, int i, int n) { int count_0 = 0; // If the state has been solved before if (dp[i, k] != -1) return dp[i, k]; // If only 1 part is left then the // remaining part of the string will // be considered as that part if (k == 1) { // To store the count of 0s and the // total characters of the string int total = n - i; // Count the 0s while (i < n) if (s[i++] == '0') count_0++; // Memoize and return the updated cost dp[i, k] = cost + (count_0 * (total - count_0)); return dp[i, k]; } int curr_cost = int.MaxValue; count_0 = 0; // Check all the positions to // make the current partition for (int j = i; j < n - k + 1; j++) { // Count the numbers of 0s if (s[j] == '0') count_0++; int curr_partlength = j - i + 1; // Cost of partition is equal to // (no. of 0s) * (no. of 1s) int part_cost = (count_0 * (curr_partlength - count_0)); // string, partitions, curr cost, // start index,.Length part_cost += minCost(s, k - 1, 0, j + 1, n); // Update the current cost curr_cost = Math.Min(curr_cost, part_cost); } // Memoize and return the updated cost dp[i, k] = (cost + curr_cost); return (cost + curr_cost); } // Driver code public static void Main (String[] args) { String s = "110101"; int n = s.Length; int k = 3; // Initialise the dp array for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) dp[i, j] = -1; } // string, partitions, curr cost, // start index,.Length Console.WriteLine(minCost(s, k, 0, 0, n)); } }// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach let MAX = 1001; // dp[i][j] will store the minimum cost // of partitioning the string into j // parts starting at the ith index let dp = new Array(MAX); // Recursive function to find // the minimum cost required function minCost(s, k, cost, i, n) { // If the state has been solved before if (dp[i][k] != -1) return dp[i][k]; // If only 1 part is left then the // remaining part of the string will // be considered as that part if (k == 1) { // To store the count of 0s and the // total characters of the string let count_0 = 0, total = n - i; // Count the 0s while (i < n) if (s[i++] == '0') count_0++; // Memoize and return the updated cost dp[i][k] = cost + (count_0 * (total - count_0)); return dp[i][k]; } let curr_cost = Number.MAX_VALUE; let count_0 = 0; // Check all the positions to // make the current partition for (let j = i; j < n - k + 1; j++) { // Count the numbers of 0s if (s[j] == '0') count_0++; let curr_part_length = j - i + 1; // Cost of partition is equal to // (no. of 0s) * (no. of 1s) let part_cost = (count_0 * (curr_part_length - count_0)); // string, partitions, curr cost, // start index, length part_cost += minCost(s, k - 1, 0, j + 1, n); // Update the current cost curr_cost = Math.min(curr_cost, part_cost); } // Memoize and return the updated cost dp[i][k] = (cost + curr_cost); return (cost + curr_cost); } let s = "110101"; let n = s.length; let k = 3; // Initialise the dp array for (let i = 0; i < MAX; i++) { dp[i] = new Array(MAX); for (let j = 0; j < MAX; j++) dp[i][j] = -1; } // string, partitions, curr cost, // start index, length document.write(minCost(s, k, 0, 0, n)); // This code is contributed by divyeshrabadiya07.</script> |
Output:
2
Time Complexity: O((n – k) + (MAX * MAX))
Auxiliary Space: O(MAX * MAX)
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!