Xử lý chuỗi
Mô tả
Team DevOps của Zalo vừa chuyển hệ thống tự động hóa phân phối bản dựng Android sang GitHub Actions. Mỗi sáng, anh cả Phòng Kiểm thử lại gửi lên chat một đoạn file cấu hình pipeline vội vã sao chép, nhưng đôi khi thiếu vài dấu ngoặc do bôi đen thiếu hoặc copy lỗi. Một pipeline chỉ chạy mượt khi mọi dấu ngoặc tròn ( và ) đều khớp đúng cặp và đúng thứ tự đóng mở.
Nhiệm vụ của bạn là viết một công cụ nhỏ: cho trước một chuỗi chỉ gồm ( và ), hãy đếm số dấu ngoặc ít nhất cần chèn thêm vào các vị trí bất kỳ để chuỗi trở thành một dãy ngoặc hợp lệ.
Đầu vào
- Một chuỗi
sgồm duy nhất các ký tự(và).
Đầu ra
- Một số nguyên duy nhất là số dấu ngoặc tối thiểu cần chèn thêm.
Ràng buộc
- Độ dài chuỗi
sthỏa mãn1 <= |s| <= 1000.
Ví dụ
Ví dụ 1:
- Đầu vào:
())) - Đầu ra:
2 - Giải thích: Chuỗi hiện tại chỉ có một dấu
(nhưng tới ba dấu). Ta có thể chèn thêm một(ở đầu và một(ngay trước))cuối để được((())), vậy cần chèn ít nhất 2 dấu.
Ví dụ 2:
- Đầu vào:
()() - Đầu ra:
0 - Giải thích: Chuỗi đã khớp ngoặc hoàn chỉnh, không cần chèn thêm dấu nào.