Given a string of paranthesis of characters “(” and “)”, such that frequency of both are same. Now certain queries are provided where characters between two indices are swapped. For each query it is to be printed whether the string is balanced or not.
To solve this question we can make use of the following property -
Let at index i , openi be the count of “(” symbol from index 0 to i and similarly closei be the count of “)” symbol.
Also let diffi be the difference between openi and closei i.e diffi = openi - closei.
Now for the string to be balanced , for all 0 <= i <= N-2 , diffi should be >= 0 and for i = N-1, diffi should be = 0. (Here N is the size of the string). Note that the second condition is always maintained because count of both symbols in the whole string is same throughout the problem.
Let for each Query Q, we get indices i and j as input. Thus characters at i and j will be swapped.
If both the characters are same, then no change will come and the answer will be same as previous state of the string.
If first character is “)” and second character is “(” , then after swapping, for indices “ind” in the range [i , j-1], the value of diffind will increase by 2.
If first character is “(” and second character is “)” , then after swapping, for indices “ind” in the range [i , j-1], the value of diffind will decrease by 2.
Thus after each swap, we need to update the diffi values in the said range and check for minimum diffi in the whole string. If the minimum diffi is >=0 , then the string will be balanced otherwise imbalanced. Segment tree can be used to store the minimum value for diffi.