Xóa cặp "01" hoặc "10" khỏi chuỗi nhị phân trong C++

Giới thiệu

Cho chuỗi nhị phân. Lặp lại xóa các cặp "01" hoặc "10" liền kề cho đến khi không còn cặp nào. Tìm số lần xóa tối thiểu.

Quan sát quan trọng

Mỗi lần xóa "01" hoặc "10" loại bỏ một 0 và một 1.

→ Số cặp xóa tối đa = min(số lượng 0, số lượng 1)

Chuỗi kết quả sẽ chỉ chứa toàn 0 hoặc toàn 1.

Ví dụ

Chuỗi: "101010001"

Số 0: 5, Số 1: 4

min(5, 4) = 4 cặp

Kết quả: "0" (còn lại 1 số 0)

Mã nguồn hoàn chỉnh

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

int findMinDeletions(string str) {
    int zeros = 0, ones = 0;
    for (char c : str) {
        if (c == '0') zeros++;
        else ones++;
    }
    return min(zeros, ones);
}

int main() {
    string str = "101010001";
    cout << "So cap can xoa: " << findMinDeletions(str) << endl;
    return 0;
}

Kết quả chạy chương trình

So cap can xoa: 4

Chứng minh tính đúng đắn

Mỗi phép xóa loại bỏ 1 cặp (0,1). Tổng số cặp có thể tạo = min(count(0), count(1)).

Luôn có thể đạt được số này bằng cách lặp lại xóa cặp liền kề bất kỳ (01 hoặc 10).

Mô phỏng quá trình xóa (để hiểu rõ)

string simulateDeletion(string s) {
    string stack;
    for (char c : s) {
        if (!stack.empty() && stack.back() != c) {
            stack.pop_back(); // Xóa cặp 01 hoặc 10
        } else {
            stack.push_back(c);
        }
    }
    return stack; // Chuỗi còn lại sau khi xóa hết cặp
}

// Test
// "101010001" → "0" (đúng, 1 số 0 còn lại = 5-4)

Phân tích độ phức tạp

• Đếm trực tiếp: O(n) thời gian, O(1) không gian
• Mô phỏng stack: O(n) thời gian, O(n) không gian

Kết luận

Bài toán đơn giản hóa nhờ nhận ra mỗi phép xóa loại bỏ 1 cặp (0,1). Kết quả chỉ phụ thuộc vào tần suất 0 và 1, không phụ thuộc thứ tự.