การลบซับสตริง "01" หรือ "10" ในสตริงไบนารี เพื่อให้ไม่มีรูปแบบเหล่านี้ใน C++

โจทย์: ให้สตริงไบนารี ต้องการหาจำนวนครั้งขั้นต่ำที่ต้องลบซับสตริง "01" หรือ "10" จนสตริงไม่มีรูปแบบเหล่านี้เหลืออยู่

ข้อสังเกตสำคัญ

การลบ "01" หรือ "10" ทีละคู่นั้นเทียบเท่ากับการจับคู่ 0 กับ 1 แล้วเอาออก จำนวนครั้งสูงสุดที่ทำได้เท่ากับจำนวนของตัวเลขที่น้อยกว่าระหว่าง 0 และ 1

ตัวอย่างโค้ด C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int deleteSubstr(string str, int length) {
    int count_0 = 0, count_1 = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == '0')
            count_0++;
        else
            count_1++;
    }
    return min(count_0, count_1);
}

int main() {
    string str = "01010110011";
    int length = str.length();
    cout << "Count of substring deletion " << deleteSubstr(str, length);
    return 0;
}

ผลลัพธ์

Count of substring deletion 5

คำอธิบาย: สตริง "01010110011" มี 0 อยู่ 5 ตัว และ 1 อยู่ 6 ตัว ดังนั้นสามารถจับคู่ลบได้ 5 คู่ (min(5,6) = 5)