Số ngoặc tối thiểu cần thêm để cân bằng chuỗi ngoặc trong C++

Cho chuỗi chỉ chứa '(' và ')'. Thêm ít nhất bao nhiêu ngoặc để chuỗi cân bằng.

Thuật toán (Đếm ngoặc mở dư)

• Duyệt chuỗi: gặp '(' → open++; gặp ')': nếu open>0 → open--, else close++.
• Kết quả = open + close.

Ví dụ triển khai (C++)

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

class Solution {
public:
    int solve(string s) {
        int open = 0, close = 0;
        for (char c : s) {
            if (c == '(') open++;
            else { if (open) open--; else close++; }
        }
        return open + close;
    }
};

int main() {
    Solution ob;
    cout << ob.solve("(()))(");
    return 0;
}

Đầu ra

2