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