Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations:Check whether the sequence is correctly bracketedRotate bracket at position $i$I dont want a solution, but some feedback if I am on a good way.There is no time complexity constraint in the instructions. So I suppose, it should be better than $O(N)$. Because trivial solution with stack leads to $O(N)$.The only options are:It can be done in logarithmic time by use of some smart tree data structure.Or it can be done in amortized constant time which I actually believe to.I have following ideas:Define function $w(i)$ for each position $i$ by $w(0)=0$ and $w(i)=w(i-1)+d_i$ where $d_i=+1$ if the bracket is $($ and $d_i=-1$ otherwise. First bracket have index $1$.Fact: The sequence is not correctly bracketed if and only if $w(N) > 0$ or there exists such $j$ for that: $w(j) < 0$.So I want to keep tracking mimum $m$ of those $w(i)$. And for the first query I able to answer in constant time just by checking that $m < 0$ and $w(N) > 0$.The problem is how to track the value of $m$ to achieve the best time.If I rotate bracket on position $i$, all $w(i)$ from $i$ to $N$ are changed by constant $\pm2$. It implies the change of $m$. If I would update those $w(i)$ directly it would lead to again to linear time.So I was wondering how to enclose this behaviour to another datastructure (post is here) in some smart way. But I just cant get over that. Everything I was thinking about is just linear. So is it possible at all?
Correct bracketing check with rotate operation on position i
data structures;context free;strings;parsers