ลบคู่ "01" หรือ "10" ในสตริงฐานสองจนไม่เหลือคู่ใน C++

บทนำ

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

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

การลบ "01" หรือ "10" ทั้งคู่ก็คือการลบ 0 หนึ่งตัวและ 1 หนึ่งตัว จำนวนคู่ที่ลบได้สูงสุด = min(จำนวน 0, จำนวน 1)

ขั้นตอนการแก้ปัญหา

1. นับจำนวน 0 และ 1 ในสตริง
2. คืนค่า min(count0, count1)

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

#include <bits/stdc++.h>
using namespace std;

int findMinimumNumberOfDeletions(string str, int len) {
    int zeroes_count = 0, ones_count = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == '0') {
            zeroes_count++;
        } else {
            ones_count++;
        }
    }
    return min(zeroes_count, ones_count);
}

int main() {
    string str = "101010001";
    int len = str.length();
    cout << findMinimumNumberOfDeletions(str, len) << endl;
    return 0;
}

ผลลัพธ์

4

คำอธิบายตัวอย่าง

"101010001": 0 มี 5 ตัว, 1 มี 4 ตัว → min(5,4) = 4 คู่ หลังลบ 4 คู่ จะเหลือ 0 เพียง 1 ตัว (ไม่มี 1 ให้จับคู่แล้ว)

สรุป

โจทย์ลดรูปได้เป็นการนับตัวอักษร ไม่ต้อง simulate การลบจริง O(n) เวลา O(1) พื้นที่