Do you think IIT Guwahati certified course can help you in your career?
Introduction
This article will discuss the problem "Minimize cost to convert all characters of a binary string to 0s", in which we have to find the minimum cost to convert all characters of a binary string to 0s. Before understanding the problem, first, recall what a binary string is.
A binary string is a string that contains either '0' or '1'.
This problem involves using simple concepts of strings and priority queues. It is a fairly straightforward problem. You can also check out the Data Structurearticles to revise your concepts before moving on to the problem.
We get a binary string 'S' and two arrayscontaining integers in this problem. The two integer arrays are "right[]" and "cost[]". It is given that there will be a cost of 'cost[i]' to flip all the characters of 'S' from index 'i' to 'right[i]'. And, we have to find the minimum cost to convert all characters of the given binary string to 0s.
Let’s take an example to understand the question:
Assume given S = “10010” ,
right[5] = {1, 3, 3, 4, 4} and
cost[5] = {3, 4, 6, 2, 1}
We have to find the minimum cost to convert the given binary string 'S' to "00000". We can flip characters in the string from index 'i' to index' right[i]' with a cost of cost[i].
Now, we have understood the question. Let's discuss the approach to find the minimum cost to convert all characters of a binary string to 0s in the next section.
Solution Approach
We will be using a greedy approach to find the minimum cost to convert all characters of a binary string to 0s. The approach is to traverse the string from left to right, and if the current character is not '0', we need to convert all the characters from the current index 'i' to 'right[i]'. After flipping the characters, we will store the index up to which we have flipped the characters to keep track of the flipped characters, and along with it, we will keep track of the total number of flips of the current character. Also, we will declare a variable for storing the minimum cost, and whenever we flip characters, we will add its cost to the minimum cost variable. In this way, after traversing the whole string, we will find the minimum cost to convert all the characters of a binary string to 0s.
Algorithm
Step 1. Create a function "minimizeCost()" .to find the minimum cost to convert all characters of a binary string to 0s. It will take the following input:
S - Given binary string
N - Length of given binary string
right[] - Given array of right indices
cost[] - Given array of cost
Step 2. Initialize two variables ‘current_flips = 0’ and ‘min_cost = 0’ to store the number of flips of the current character and minimum cost to convert all characters of a binary string to 0s respectively.
Step 3 Create a priority queue to store the indices up to which number of flips is greater than zero and which will store the lowest element at the top.
Step 4. Now traverse the string from left to right and if the number of flips for the current character is odd, then update it. Then check if it is not equal to ‘0’, flip it, increase the value of ‘current_flip’ and ‘min_cost’, and insert the value of right[i] into the priority queue.
Step 5. Finally, after traversing the string, return the calculated value of minimum cost to convert all the characters of a binary string to 0s.
C++ Code
// C++ code to find the minimum cost to convert all characters of a binary string to 0s
#include <bits/stdc++.h>
using namespace std;
//Function to find minimum cost to convert all characters of a binary string to 0s
int minimizeCost(string s, int n, int right[], int cost[])
{
/*
Priority queue to store the right indices
upto which characters are flipped
*/
priority_queue<int, vector<int>, greater<int> > pq;
// Variable to store the minimum cost
int min_cost = 0;
// Variable to store the number of flips of current character
int current_flip = 0;
// Traverse the string from left to right
for (int i = 0; i < n; i++)
{
// Remove the indices which are left of the current index
while (pq.size() > 0 and pq.top() < i)
{
pq.pop();
/*
Decrease the value of current flip as we are
removing one flip from the priority queue
*/
current_flip--;
}
// Check if current_flip is odd, then flip the current character
if (current_flip % 2 == 1)
{
if(s[i]=='1') {
s[i]='0';
}
else s[i]='1';
}
// Now, check if current character is '1', then flip it
if (s[i] == '1')
{
// Increase the count of current_flip
current_flip++;
// Increase the min_cost by cost[i]
min_cost += cost[i];
/*
As we have now flipped till right[i],
add the right[i] index in priority queue
*/
pq.push(right[i]);
}
}
// Return the calculated minimum cost
return min_cost;
}
int main()
{
string s = "10010";
int right[] = {1, 3, 3, 4, 4};
int cost[] = {3, 4, 6, 2, 1};
// Find the length of the given string
int n = s.length();
/*
Call the function to find minimum cost to
convert all characters of a binary string to 0s
*/
int minimumCost = minimizeCost(s, n, right, cost);
cout<<"The minimum cost to convert all characters of given binary string to 0s is "<<minimumCost<<endl;
}
You can also try this code with Online C++ Compiler
In the function "minimizeCost()" to find the minimum cost to convert all characters of a binary string to 0s, we have created a priority queue and inserted elements of the given binary string into it and the time complexity of inserting an element to priority queue is O(log(N)). So, time complexity will be O(Nlog(N)), where ‘N’ is the length of the given binary string.
Space Complexity: O(N)
In the function "minimizeCost()" to find the minimum cost to convert all characters of a binary string to 0s, we have created a priority queue and inserted elements of the given binary string. So, the space complexity will be O(N)
Frequently Asked Questions
What is the time complexity of inserting an element into a priority queue?
The time complexity of inserting an element into a priority queue is O(logN), where ‘N’ is the number of elements in it.
Why we have used a priority queue which is storing the minimum value at its top?
As we are traversing the string from left to right and fixing the elements from left to right. We need to get first the minimum index which is flipped so that first we can process it and then move ahead. So, we need to store the indices in the priority queue in such a way that the minimum index will be at the top.
Conclusion
This article discussed the problem of finding the minimum cost to convert all characters of a binary string to 0s, the approach to solving it, its C++ implementation, and its time and space complexities. If you want to practice problems with data structures and algorithms then you can visit Coding Ninjas Studio.
40+ registered 
