Tutorial — Ngoặc Chuẩn

Việc xóa một số ký tự để thu được chuỗi ngoặc chuẩn dài nhất tương đương với việc ghép cặp nhiều nhất có thể giữa các dấu mở ngoặc và dấu đóng ngoặc. Mỗi cặp ghép phải đảm bảo vị trí dấu mở ngoặc đứng trước vị trí dấu đóng ngoặc.

Khi duyệt tuần tự từ trái qua phải, mỗi khi gặp một dấu đóng ngoặc, việc ghép đôi ngay với một dấu mở ngoặc khả dụng trước đó không bao giờ làm giảm cơ hội ghép của các ký tự phía sau. Một dấu đóng ngoặc xuất hiện khi không còn dấu mở ngoặc nào khả dụng chắc chắn không thể tham gia vào bất kỳ cặp ghép hợp lệ nào.

Sử dụng thuật toán tham lam bằng cách duy trì số lượng dấu mở ngoặc chưa ghép khi duyệt qua chuỗi: tăng số lượng này khi gặp mở ngoặc, và khi gặp đóng ngoặc nếu số lượng mở ngoặc khả dụng lớn hơn $0$ thì trừ đi $1$ đồng thời tăng số cặp ghép. Kết quả cần in ra là số cặp ghép nhân đôi.