Các bước tối thiểu để xóa chuỗi con 010 khỏi chuỗi nhị phân trong C ++

Tuyên bố vấn đề

Cho một chuỗi nhị phân, nhiệm vụ là đếm các bước tối thiểu để xóa chuỗi con 010 khỏi chuỗi nhị phân này

Ví dụ

Nếu chuỗi đầu vào là 010010 thì bắt buộc phải thực hiện 2 bước

• Chuyển đổi đầu tiên 0 thành 1. Chuỗi bây giờ trở thành 110010
• Chuyển đổi cuối cùng từ 0 thành 1. Giờ đây, chuỗi cuối cùng trở thành 110011

Thuật toán

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

Ví dụ

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

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum required steps = 2