最小化翻转次数，使得字符串不包含任何连续的0

---

这里，我们需要操作二进制字符串，使其不包含任何连续的零。如果我们找到连续的零，我们需要将任何一个零改为1。因此，我们需要计算为了去除字符串中所有连续的零而应该进行的0到1转换的总数。

问题陈述 − 我们给定一个仅包含0和1的二进制字符串“str”。我们需要找到所需的最小翻转次数，以使生成的字符串不包含任何连续的零。

示例

Input –  0101001

Output – 1

解释

我们只需要翻转最后一个零。

Input –  str = 00100000100

Output – 4

解释

我们需要翻转第2、5、7和11个零以去除所有连续的零对。

Input –  0101010101

Output – 0

解释

我们不需要进行任何翻转，因为字符串不包含连续的零。

方法1

在这种方法中，我们将从头到尾迭代字符串，如果字符串包含任何连续的零，则翻转字符。最后，我们可以得到从给定的二进制字符串中去除所有连续零所需的最小翻转总数。

算法

• 步骤1 − 将“cnt”变量初始化为零，存储翻转总数。

• 步骤2 − 使用循环遍历二进制字符串。

• 步骤3 − 如果索引“I”和索引“I + 1”处的字符为0，则翻转下一个字符，并将“cnt”变量的值增加1。

• 步骤4 − 当for循环迭代完成时，返回“cnt”的值。

示例

#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;
}

输出

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

时间复杂度 − O(N)，因为我们遍历二进制字符串。

空间复杂度 − O(1)，因为我们使用常量空间来存储总数。

结论

我们学习了如何计算从给定的二进制字符串中去除连续零对所需的最小翻转次数。用户可以尝试计算从给定的二进制字符串中去除连续一对一的最小翻转次数。