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 bracketed
- Rotate 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?