I was working on
My half solution :
Replace all the '(' with 1 and ')' with -1 and construct a new array A[ ]. ( A[i] = 1 or -1 )
calculate C[ ]. ( C[i] is the sum of the values A...A[i] )
Now, for determining whether the word is correct or not you need to check if A[ ] sums up to zero and if any of the C[i]'s are negative.
The first check can be done easily.
To do the second check, build a segment tree from C[ ], where each node is a pair<int,int>. Here, pair.first is the index of the minimum in the corresponding range and pair.second is the total value added in that range without considering the parents. For the replacement operations add 2 [ for ')' to '(' ] or -2 [ for '(' to ')' ] with all the values in C[i...n]. The replacement is performed in the i-th position. This can be done in log(n) with the segment tree.
But, how can I find the minimum in C[ ], in less than O(n), using this segment tree? Do I need to add any extra information or perform any special operation?
I am new to the concept of segment trees.
Thanks in advance and sorry for the long description.