Translate the following into Chinese: Minimize the removal of 0 substrings to remove all occurrences of 0 from a looped binary string

In this problem, we need to remove all zeros from the given binary string. At the same time, we need to remove consecutive pairs of zeros at once and count the total number of removed zero pairs.

We can solve the problem by counting the number of pairs of consecutive zeros in the given string. In this tutorial, we will learn two different solutions to solve the problem.

Problem Statement − We are given a circular binary string str of length N. We need to find the minimum number of consecutive zeros required to remove all zeros from the string.

ExampleExample

Input –  str = "0011001"

Output – 2

Explanation

We can delete str[0] and str[1] together. After that, we can delete str[4] and str[5]. So, we need to remove 2 pairs of consecutive zeros.

Input –  str = ‘0000000’

Output – 1

Explanation

We can remove all zeros at once.

Input –  str = ‘00110010’

Output – 2

Explanation

We can remove str[0], str[1], and str[7] together as the binary string is circular. Next, we can remove str[5] and str[6] together.

Approach 1

In this method we will find the total number of consecutive zero pairs in the given string, which will answer the given question.

Algorithm

• Step 1 - Initialize the 'cnt' variable to zero.

• Step 2 - Initialize the 'isOne' variable to a false value to keep track of the number 1 in the given string.

• Step 3 - Iterate over the string using a loop. In the loop, if the current character is '0', increase the value of 'cnt' by 1.

• Step 4 − Use a while loop to iterate until we continue to find the next character which is '0' and increase the value of 'I' by 1.

• Step 5 - If the current character is '1', change the value of the 'isOne' variable to true, indicating that the string contains at least one '1'.

• Step 6 − Once the iteration of the loop completes, If the value of 'isOne' is false, it means the string contains only zeros. Return 1 in such cases.

• Step 7 − If the first and last characters are ‘0’, decrease the value of the ‘cnt’ by 1 as the string is circular.

• Step 8 − Return the value of ‘cnt’.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   bool isOne = false;
   
   // Iterate over the string
   for (int i = 0; i < N; i++){
   
      // If the current character is 0, increment the count of 0s
      if (str[i] == '0'){
         cnt++;
         
         // traverse the string until a 1 is found
         while (str[i] == '0'){
            i++;
         }
      }
      else{
      
         // If the current character is 1, then set isOne as true
         isOne = true;
      }
   }
   
   // If string contains only 0s, then return 1.
   if (!isOne)
      return 1;
      
   // If the first and last character is 0, then decrement the count, as the string is circular.
   if (str[0] == '0' && str[N - 1] == '0'){
      cnt--;
   }
   
   // return cnt
   return cnt;
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

Output

The total number of minimum substrings of consecutive zeros required to remove is - 2<font face="sans-serif"><span style="font-size: 16px; background-color: rgb(255, 255, 255);">.</span></font></p><p>

Space complexity - O(1)

Method Two

In this method, we will calculate the minimum number of zero-removal substrings required in order to remove all zeros by counting the differences of adjacent elements.

Algorithm

• Step 1 − Define the ‘cnt’ and ‘isOne’ variables, and initialize with 0 and false, respectively.

• Step 2 − Use for loop to make N-1 iterations, where N is the length of the string.

• Step 3 − In the loop, check if the current character is '0,' and the next character is '1', increase the value of 'cnt' by 1. Otherwise, change the value of the 'isOne' variable to true.

• Step 4 - If the last character is '0', and the first character is '1', then increase the value of 'cnt' by 1.

• Step 5 - If the value of 'isOne' is false, return 1.

• Step 6 - Return the value of the ‘cnt’ variable.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   
   // to check if there is at least one 1
   bool isOne = false;
   
   // traverse the string
   for (int i = 0; i < N - 1; i++) {
   
      // if the current character is 0, the next is 1, then increment count by 1
      if (str[i] == '0' && str[i + 1] == '1'){
         cnt++;
      }
      else{
      
         // if the current character is 1, then set isOne to true
         isOne = true;
      }
   }
   
   // for circular string, if the last character is 0 and the first is 1, then increment count by 1
   if (str[N - 1] == '0' && str[0] == '1'){
      cnt++;
   }
   
   // if there is no 1 in the string, then return 1
   if (!isOne){
      return 1;
   }
   return cnt; // return cnt
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

Output

The total number of minimum substrings of consecutive zeros required to remove is - 2

in conclusion

We have seen two different solutions to the given problem. In the first method we count the total number of consecutive zero pairs, in the second method we count the total number of unmatched adjacent characters.

The above is the detailed content of Translate the following into Chinese: Minimize the removal of 0 substrings to remove all occurrences of 0 from a looped binary string. For more information, please follow other related articles on the PHP Chinese website!