GeeksforGeeks App
Open App
Browser
Continue

# Minimum cost of flipping characters required to convert Binary String to 0s only

Given binary string str, and integers A, which denotes the cost of converting consecutive 1s to 0s, and B, which denotes the cost of converting 0s to 1s. The task is to find the minimum cost to reduce the string str to 0s only.

Examples:

Input: str = “01101110”, A = 5, B = 1
Output: 6
Explanation:
Convert the str[3] to ‘1’. Cost = 1, str = “01111110”.
Convert the substring {str[1], … str[6]} to ‘0’. Cost = 5, str = “00000000”.

Input: str = “1010010011110111”, A = 12, B = 14
Output: 60

Approach: The given problem can be solved based on the following observations:

For any pair of consecutive segments of 1s [L1, R1] and [L2, R2] (where L2 > R1), choose to either convert both segments to 0s for a cost of 2 * A or convert 0s between both these segments to 1s and convert [L1, R2] to 1s for a cost of A + (L2 – R1 – 1) * B.

Follow the steps below to solve the problem:

• Initialize a variable left_1 and store the index of leftmost ‘1’ in str
• Initialize another variable right_1 and store the index of rightmost ‘1’ in str.
• If left_1 and right_1 do not exist, then str already consists of 0s only. Therefore, print 0 as the minimum cost
• Otherwise, there is at least one ‘1’ in str. Therefore, initialize cost = A.
• Iterate over the characters in string str from left_1 to right_1 with a pointer i
• Calculate the number of consecutive 0s to the right of i and store it in variable zeroes.
• If the length of zeroes exceeds 0, convert 0s to 1s for a cost of zeroes * B or convert consecutive 1s to 0s for the cost of A.
• Therefore, increment cost by min(zeroes * B, A)
• Finally, print the minimum cost obtained.

Below is the implementation of the above approach:

## C++

 `// C++ Program to implement``// the above approach``#include ``using` `namespace` `std;` `// Function to find the minimum cost``// to convert given string to 0s only``void` `convert_to_allzeroes(string str,``                          ``int` `a, ``int` `b)``{``    ``// Length of string``    ``int` `len = str.length();` `    ``// Stores the index of leftmost '1' in str``    ``int` `left_1, i = 0;` `    ``while` `(i < len && str[i] == ``'0'``)``        ``i++;` `    ``// Update the index of leftmost '1' in str``    ``left_1 = i;` `    ``// Stores the index of rightmost '1' in str``    ``int` `right_1;``    ``i = len - 1;``    ``while` `(i >= 0 && str[i] == ``'0'``)``        ``i--;` `    ``// Update the index of rightmost '1' in str``    ``right_1 = i;` `    ``// If str does not contain any '1's``    ``if` `(left_1 == len && right_1 == -1) {` `        ``// No changes required``        ``cout << 0;``        ``return``;``    ``}` `    ``// Stores minimum cost``    ``int` `cost = a, zeroes;` `    ``// Iterating through str form``    ``// left_1 to right_1``    ``for` `(i = left_1; i <= right_1; i++) {` `        ``// Stores length of``        ``// consecutive 0s``        ``zeroes = 0;` `        ``// Calculate length of consecutive 0s``        ``while` `(i < len && str[i] == ``'0'``) {` `            ``zeroes++;``            ``i++;``        ``}` `        ``// If a substring of 0s exists``        ``if` `(zeroes)` `            ``// Update minimum cost``            ``cost += min(zeroes * b, a);``    ``}``    ``// Printing the minimum cost``    ``cout << cost;``}` `// Driver Code``int` `main()``{``    ``string str = ``"01101110"``;``    ``int` `A = 5, B = 1;``    ``convert_to_allzeroes(str, A, B);``    ``return` `0;``}`

## Java

 `// Java program to implement``// the above approach``class` `GFG{``    ` `// Function to find the minimum cost``// to convert given string to 0s only``public` `static` `void` `convert_to_allzeroes(String str,``                                        ``int` `a, ``int` `b)``{``    ` `    ``// Length of string``    ``int` `len = str.length();``  ` `    ``// Stores the index of leftmost '1' in str``    ``int` `left_1, i = ``0``;``  ` `    ``while` `(i < len && str.charAt(i) == ``'0'``)``        ``i++;``  ` `    ``// Update the index of leftmost '1' in str``    ``left_1 = i;``  ` `    ``// Stores the index of rightmost '1' in str``    ``int` `right_1;``    ``i = len - ``1``;``    ` `    ``while` `(i >= ``0` `&& str.charAt(i) == ``'0'``)``        ``i--;``  ` `    ``// Update the index of rightmost '1' in str``    ``right_1 = i;``  ` `    ``// If str does not contain any '1's``    ``if` `(left_1 == len && right_1 == -``1``)``    ``{``        ` `        ``// No changes required``        ``System.out.print(``0``);``        ``return``;``    ``}``  ` `    ``// Stores minimum cost``    ``int` `cost = a, zeroes;``  ` `    ``// Iterating through str form``    ``// left_1 to right_1``    ``for``(i = left_1; i <= right_1; i++)``    ``{``        ` `        ``// Stores length of``        ``// consecutive 0s``        ``zeroes = ``0``;``  ` `        ``// Calculate length of consecutive 0s``        ``while` `(i < len && str.charAt(i) == ``'0'``)``        ``{``            ``zeroes++;``            ``i++;``        ``}``  ` `        ``// If a substring of 0s exists``        ``if` `(zeroes != ``0``)``  ` `            ``// Update minimum cost``            ``cost += Math.min(zeroes * b, a);``    ``}``    ` `    ``// Printing the minimum cost``    ``System.out.print(cost);``}` `// Driver code``public` `static` `void` `main(String[] args)``{``    ``String str = ``"01101110"``;``    ``int` `A = ``5``, B = ``1``;``    ` `    ``convert_to_allzeroes(str, A, B);``}``}` `// This code is contributed by divyeshrabadiya07`

## Python3

 `# Python3 Program to implement``# the above approach` `# Function to find the minimum``# cost to convert given string``# to 0s only``def` `convert_to_allzeroes(st,``                         ``a, b):` `    ``# Length of string``    ``length ``=` `len``(st)` `    ``# Stores the index of``    ``# leftmost '1' in str``    ``left_1 ``=` `0``    ``i ``=` `0` `    ``while` `(i < length ``and``           ``st[i] ``=``=` `'0'``):``        ``i ``+``=` `1` `    ``# Update the index of``    ``# leftmost '1' in str``    ``left_1 ``=` `i` `    ``# Stores the index of``    ``# rightmost '1' in str``    ``right_1 ``=` `0``    ``i ``=` `length ``-` `1``    ` `    ``while` `(i >``=` `0` `and``           ``st[i] ``=``=` `'0'``):``        ``i ``-``=` `1` `    ``# Update the index of``    ``# rightmost '1' in str``    ``right_1 ``=` `i` `    ``# If str does not contain``    ``# any '1's``    ``if` `(left_1 ``=``=` `length ``and``        ``right_1 ``=``=` `-``1``):` `        ``# No changes required``        ``print``(``0``)``        ``return` `    ``# Stores minimum cost``    ``cost ``=` `a` `    ``# Iterating through str form``    ``# left_1 to right_1``    ``for` `i ``in` `range``(left_1,``                   ``right_1 ``+` `1``):` `        ``# Stores length of``        ``# consecutive 0s``        ``zeroes ``=` `0` `        ``# Calculate length of``        ``# consecutive 0s``        ``while` `(i < length ``and``               ``st[i] ``=``=` `'0'``):``            ``zeroes ``+``=` `1``            ``i ``+``=` `1` `        ``# If a substring of``        ``# 0s exists``        ``if` `(zeroes):` `            ``# Update minimum cost``            ``cost ``+``=` `min``(zeroes ``*` `b, a)` `    ``# Printing the minimum cost``    ``print``(cost)` `# Driver Code``if` `__name__ ``=``=` `"__main__"``:` `    ``st ``=` `"01101110"``    ``A ``=` `5``    ``B ``=` `1``    ``convert_to_allzeroes(st, A, B)` `# This code is contributed by Chitranayal`

## C#

 `// C# program to implement``// the above approach ``using` `System;` `class` `GFG{``     ` `// Function to find the minimum cost``// to convert given string to 0s only``public` `static` `void` `convert_to_allzeroes(``string` `str,``                                        ``int` `a, ``int` `b)``{``    ` `    ``// Length of string``    ``int` `len = str.Length;``   ` `    ``// Stores the index of leftmost '1' in str``    ``int` `left_1, i = 0;``   ` `    ``while` `(i < len && str[i] == ``'0'``)``        ``i++;``   ` `    ``// Update the index of leftmost '1' in str``    ``left_1 = i;``   ` `    ``// Stores the index of rightmost '1' in str``    ``int` `right_1;``    ``i = len - 1;``     ` `    ``while` `(i >= 0 && str[i] == ``'0'``)``        ``i--;``   ` `    ``// Update the index of rightmost '1' in str``    ``right_1 = i;``   ` `    ``// If str does not contain any '1's``    ``if` `(left_1 == len && right_1 == -1)``    ``{``        ` `        ``// No changes required``        ``Console.Write(0);``        ``return``;``    ``}``   ` `    ``// Stores minimum cost``    ``int` `cost = a, zeroes;``   ` `    ``// Iterating through str form``    ``// left_1 to right_1``    ``for``(i = left_1; i <= right_1; i++)``    ``{``        ` `        ``// Stores length of``        ``// consecutive 0s``        ``zeroes = 0;``   ` `        ``// Calculate length of consecutive 0s``        ``while` `(i < len && str[i] == ``'0'``)``        ``{``            ``zeroes++;``            ``i++;``        ``}``   ` `        ``// If a substring of 0s exists``        ``if` `(zeroes != 0)``        ` `            ``// Update minimum cost``            ``cost += Math.Min(zeroes * b, a);``    ``}``     ` `    ``// Printing the minimum cost``    ``Console.Write(cost);``}`` ` `// Driver code``public` `static` `void` `Main()``{``    ``string` `str = ``"01101110"``;``    ``int` `A = 5, B = 1;``    ` `    ``convert_to_allzeroes(str, A, B);``}``}` `// This code is contributed by susmitakundugoaldanga`

## Javascript

 ``

Output:

`6`

Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(1)

My Personal Notes arrow_drop_up
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}