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

Đề bài

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

Ví dụ

Nếu chuỗi đầu vào là 010010 thì cần 2 bước

• Chuyển 0 đầu tiên thành 1. Chuỗi trở thành 110010
• Chuyển 0 cuối cùng thành 1. Chuỗi cuối cùng trở thành 110011

Thuật toán

1. Duyệt chuỗi từ chỉ số 0 đến n-2
2. Nếu trong chuỗi nhị phân có 3 ký tự liên tiếp '0', '1', '0' thì có thể thay đổi một trong các ký tự
Tăng biến đếm vòng lặp thêm 2

Ví dụ mã C++

#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 << "Số bước tối thiểu cần = " << getMinSteps(str) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số bước tối thiểu cần = 2