Minimize the number of flips so that there are no consecutive pairs of zeros in the string

Here, we require to manipulate the binary string so that it doesn't contain any consecutive zeros. If we find consecutive zeros, we need to change any zero to 1. So, we require to count the total number of 0 to 1 conversion we should make to remove all consecutive zeros from the string.

Problem Statement − We are given a binary string ‘str’ that only contains 0 and 1. We need to find the minimum number of flips required so that the resulting string does not contain consecutive zeros.

ExampleExample

Input –  0101001

Output – 1

Explanation

We need to flip only the second to last zero.

Input –  str = 00100000100

Output – 4

Explanation

We need to flip the 2nd, 5th, 7th and 11th zeros to eliminate all consecutive zero pairs.

Input –  0101010101

Output – 0

Explanation

We don't need to do any flipping since there are no consecutive zeros in the string.

method one

In this method, we will iterate over the string from beginning to end and flip the character if it contains any consecutive zeros. Finally, we can get the minimum number of flips required to remove all consecutive zeros from a given binary string.

algorithm

• Step 1 − Initialize the ‘cnt’ variable with zero, storing a total number of flips.

• Step 2 − Iterate through the binary string using the loop.

• Step 3 − If the character at index 'I' and index 'I 1' is 0, flip the next character, and increase the value of the 'cnt' variable by 1.

• Step 4 - When the iteration of the for loop completes, return the value of 'cnt'.

Example

#include <bits/stdc++.h>
using namespace std;
// Function to get the total number of minimum flips required so the string does not contain any consecutive 0’s
int findCount(string str, int len){

   // initialize the count
   int cnt = 0;
   
   // iterate over the string
   for (int i = 0; i < len - 1; i++){
   
      // If two consecutive characters are the same
      if (str[i] == '0' && str[i + 1] == '0'){
      
         // Flip the next character
         str[i + 1] = '1';
         
         // increment count
         cnt++;           
      }
   }
   return cnt;
}
int main(){
   string str = "00100000100";
   int len = str.length();
   cout << "The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - " << findCount(str, len);
   return 0;
}

Output

The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - 4

Time complexity − O(N), as we iterate through the binary string.

Space complexity − O(1), as we use constant space to store total counts.

in conclusion

We learned to calculate the minimum number of flips required to remove consecutive pairs of zeros from a given binary string. The user can try to calculate the minimum number of flips required to remove a consecutive pair from a given binary string.

The above is the detailed content of Minimize the number of flips so that there are no consecutive pairs of zeros in the string. For more information, please follow other related articles on the PHP Chinese website!