Finally, I found the way to solve it in O(n) (needs about 4 full string-checks). In journey to this solution i tried to imagine that i'm cutting brackets like '()'. And watching what I can get by cutting all this pieces. Looking on new sequence I understood what I need to shift to get right bracket-sequence.

Here are some tests that helped me:

)))(()((
ans: 1

(()(()))
ans: 1

())(
ans: 1

))(())())((()(
ans: 1

Edited by author 27.07.2012 14:19