Tutorial — Sửa Dấu Ngoặc

Hãy quy ước mỗi dấu `(` là $+1$ và mỗi dấu `)` là $-1$. Một chuỗi là chuẩn khi và chỉ khi tổng cân bằng cuối cùng bằng $0$ và mọi tổng tiền tố đều không âm, vậy tổng cân bằng ban đầu có thể nhận những giá trị nào để một phép đổi dấu đưa chuỗi về chuẩn?

Khi đảo dấu ngoặc tại vị trí $i$, tất cả các tiền tố từ vị trí $i$ trở đi đều thay đổi cùng một lượng là $+2$ hoặc $-2$, trong khi các tiền tố trước $i$ được giữ nguyên. Do đó, điều kiện hợp lệ sẽ phụ thuộc vào các tiền tố nhỏ nhất ở hai phía của vị trí $i$.

Sử dụng mảng tiền tố cộng dồn để xác định vị trí đầu tiên có tiền tố bị âm khi tổng cân bằng là $-2$, hoặc vị trí cuối cùng có tiền tố nhỏ hơn $2$ khi tổng cân bằng là $2$. Từ các mốc này, ta có thể đếm trực tiếp số lượng dấu ngoặc thỏa mãn trong thời gian $O(n)$.