Tìm chuỗi nhị phân đúng tối thiểu bằng C++

Mô tả bài toán

Cho chuỗi nhị phân S không có số 0 thừa ở đầu. Có thể thực hiện hai phép toán:

Hoán đổi hai bit liền kề bất kỳ.
Thay thế tất cả "11" bằng "1".

Giá trị val(S) là biểu diễn thập phân của S. Cần tìm chuỗi đúng có giá trị nhỏ nhất (so sánh theo val).

Ví dụ

S = "1001" → Kết quả: "100".
Quá trình: "1001" → "1010" → "1100" → "100".

Thuật toán

Quan sát: Phép thay "11" → "1" giảm độ dài chuỗi. Để giá trị nhỏ nhất, ta nên giữ lại bit đầu tiên (luôn là '1') và chỉ giữ lại các bit '0' trong chuỗi gốc. Do đó, kết quả là bit đầu tiên cộng với tất cả các bit '0' còn lại.

Khởi tạo kết quả res với ký tự đầu tiên của S.
Duyệt từ chỉ số 1 đến cuối: nếu ký tự là '0' thì nối vào res.
Trả về res.

Code C++

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

string solve(string S) {
    int n = S.size();
    string res = "";
    res += S[0];
    for (int i = 1; i < n; i++) {
        if (S[i] == '0')
            res += '0';
    }
    return res;
}

int main() {
    string S = "1001";
    cout << solve(S) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: "1001"

Output: "100"