ขั้นตอนต่ำสุดในการลบ substring 010 จากสตริงไบนารีใน C++

ข้อกำหนดโจทย์

กำหนดสตริงไบนารี งานคือนับขั้นตอนต่ำสุดในการลบ substring 010 จากสตริงไบนารีนี้

ตัวอย่าง

ถ้าสตริงอินพุตคือ 010010 แล้วต้องใช้ 2 ขั้นตอน

• แปลง 0 ตัวแรกเป็น 1 ตอนนี้สตริงกลายเป็น 110010
• แปลง 0 ตัวสุดท้ายเป็น 1 ตอนนี้สตริงสุดท้ายกลายเป็น 110011

อัลกอริทึม

1. วนลูปสตริงจากดัชนี 0 ถึง n-2
2. ถ้าในสตริงไบนารีมีตัวอักษรติดกัน 3 ตัว '0', '1', '0' ให้เปลี่ยนตัวอักษรใดตัวหนึ่ง เพิ่มตัวนับลูป 2

ตัวอย่างโค้ด 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 << "Minimum required steps = " << getMinSteps(str) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum required steps = 2