Definition:
A "Bracket String" is a string that only has '(' and ')'.
A string of balanced bracket is defined as:
- If string is empty, it's a balanced bracket
- If A is a balanced bracket,
(A)is a balanced bracket- If A and B are balanced brackets, AB is a balanced bracket
Question:
Given a string S of balanced bracket and Q queries, each query has an integer x
For each query
- Reverse S[x] (change S[x] from '(' to ')' or vice-versa)
- Find the minimum index t, so that if you reverse S[t], string S is a balanced bracket
- Reverse S[t]
This is a competitive programming problem. I solved it with brute force and got TLE for large N (size of string S) and Q. Is there any better algorithm to solve this?