Minimize cost to convert all characters of a binary string to 0s

Riya
Last Updated: May 13, 2022

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'.

We get a binary string 'S' and two arrays containing 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:

1. S - Given binary string
2. N - Length of given binary string
3. right[] - Given array of right indices
4. cost[] - Given array of cost

Step 2. Initialize two variables ‘current_flips = 0’ and  ‘min_cost = 0’ to store the number of flips of 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.

Algorithm Complexity:

Time Complexity: O(Nlog(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 to it and the time complexity of inserting an element to priority queue is O(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)

1. 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.

2. 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.

Key takeaways-

This article discussed the problem of finding the minimum cost to convert all characters of a binary string to 0s, the approach to solve it, its C++ implementation, and its time and space complexities. If you want to practice problems of data structures and algorithms then you can visit codestudio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.