Thực chất bài toán này chính là bài toán tìm xem có bao nhiêu dấu ngoặc đóng không đúng chỗ. Biến ans trong hàm solve() dùng để đếm xem cần bao nhiêu dấu ngoặc đóng nữa để tạo ra dãy dấu ngoặc hợp lệ. Nếu gặp một dấu "(" thì nghĩa là ta cộng thêm 1 vào biến ans (nghĩa là cần thêm 1 dấu ")" nữa mới tạo được dãy con hợp lệ), ngược lại, gặp dấu ")" sẽ trừ đi 1 (do đã đóng đc 1 cặp ngoặc). Nếu biến ans mà bé hơn 0, nghĩa là tồn tại dấu ngoặc đóng không được đặt đúng chỗ thì ta sẽ cập nhật biến res thành min(res, ans) do ta cần đếm xem có bao nhiêu dấu ngoặc đóng không hợp lệ. Nếu ans càng bé thì càng có nhiều dãy ngoặc không hợp lệ.

Cuối cùng, ta in ra màn hình kết quả chính là |res| (giá trị tuyệt đối của res) do số dấu ngoặc cần phải là số tự nhiên. Nếu theo như thuật toán trên thì thậm chí ta còn chẳng cần n.

Code:

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

int solve(string s){
    int ans=0,res=0;
    for(char k:s){
        if(k=='(')++ans;
        else --ans;
        res=min(res,ans);
    }
    return abs(res);
}

signed main(){
    int t;cin>>t;
    while(t--){
        string n="useless",s;cin>>n>>s;
        cout<<solve(s)<<'\n';
    }
}