Bessie cố gõ chuỗi ngoặc cân bằng trên máy tính xách tay mới, nhưng móng lớn khiến cô vụng về và gõ sai. Tìm số ký tự ít nhất phải đảo (ngoặc mở thành đóng hoặc ngược lại) để chuỗi cân bằng.

Có nhiều định nghĩa cân bằng. Đơn giản nhất là tổng số ngoặc mở và đóng bằng nhau, và trong mọi tiền tố số ngoặc mở không ít hơn số ngoặc đóng. Các chuỗi sau cân bằng:

()
(())
()(()())

Các chuỗi này không cân bằng:

)(
())(
((())))

Dữ liệu vào

• Dòng 1: chuỗi ngoặc $A$ có độ dài chẵn, tối đa 100,000 ký tự.

Dữ liệu ra

• Dòng 1: số nguyên, số ngoặc ít nhất cần đảo để chuỗi cân bằng.

Ví dụ

Dữ liệu vào 1

())(

Dữ liệu ra 1

2

Ghi chú

Phải đảo ngoặc cuối và một trong hai ngoặc đóng ở giữa.

Tác giả: Brian Dean, 2012