- binary-string, Strings, substring

Minimize cost to make all characters of a Binary String equal to ‘1’ by reversing or flipping characters of substrings

Minimize cost to make all characters of a Binary String equal to ‘1’ by reversing or flipping characters of substringsGiven a binary string S, and two integers A, which denotes the cost of reversing a substring, and B, which denotes the cost of flipping all characters of a substring, the task is to find the minimum cost to reduce the string S to 1s only.Examples:Input: S = “01100”, A = 1, B = 5Output: 6Explanation: One possible way to make all characters equal to ‘1’ is as follows:Reverse the substring {S[0], S[2]}. Cost = A (= 1), The string modifies to “11000”.Flip the characters of substring {S[2], S[4]}. Cost of B (= 5). The string modifies to “11111”.Therefore, the total cost = 5+1 = 6 (which is the minimum cost possible)Input: S = “1111111”, A = 2, B = 3Output: 0Approach: The given problem can be solved based on the following observations: Assuming there are P disjoint groups of continuous ‘0’s,If A is less than B, then it is optimal to convert P groups into ‘1’ group of continuous ‘0’s by performing the first type of operation for a cost of (P – 1) * A and then converting all the ‘0’s to ‘1’s for a cost of B.Otherwise, it is optimal to perform the second operation on each group separately, for a cost of B * P.Follow the steps below to solve the problem:Initialize a variable say P with 0 value to store the count of disjoint groups of continuous 0s.Also, initialize a variable say count as 0 to store the temporary count of the number of 0s in a group.Iterate over the character of the string S and do the following:If the current character is ‘0‘ then increment the count by 1.Otherwise, if the count is greater than 0 then increment P by 1 and then assign 0 to count.If the count is greater than 0 then increment P by 1.Print the minimum cost obtained as (P-1)*A+B.Below is the implementation of the above approach:C++#include using namespace std;  void MinimumCost(string S, int A, int B){        int count = 0;              int group = 0;          for (int i = 0; i < S.size(); i++) {                  if (S[i] == '0') {            count += 1;        }        else {                                    if (count > 0) {                group += 1;            }                          count = 0;        }    }              if (count > 0)        group += 1;              if (group == 0) {        cout