在C ++中从二进制字符串中删除子字符串010的最少步骤

问题陈述

给定一个二进制字符串，任务是计算从该二进制字符串中删除子字符串010的最少步骤

示例

如果输入字符串是010010，则需要2个步骤

• 将第一个0转换为1。现在字符串变为110010

• 将最后一个0转换为1。现在最后一个字符串变为110011

算法

1. Iterate the string from index 0 sto n-2
2. If in binary string has consecutive three characters ‘0’, ‘1’, ‘0’ then any one character can be changed
Increase the loop counter by 2

示例

#include <bits/stdc++.h>
using namespace std;
int getMinSteps(string str) { 
   int cnt = 0;
   for (int i = 0; i < str.length() - 2; ++i) {
      if (str[i] == '0' && str[i + 1] == '1' && str[i+ 2] == '0') {
         ++cnt;
         i += 2;
      }
   }
   return cnt;
}
int main() {
   string str = "010010";
   cout << "Minimum required steps = " << getMinSteps(str)
   << endl;
   return 0;
}

当您编译并执行上述程序时。它产生以下输出

输出结果

Minimum required steps = 2