### hossainzarif's blog

By hossainzarif, 2 months ago,

problem
submission
I don't know why my approach works.
I first found out the balance of every string $(number of left bracket - number of right bracket)$ and minimum balance of every string. let $bal$ be balance and $mnbal$ be minimum balance. Like $()))(($ has balance $0$ and minimum balance $-2$ (obtained at index $3$).
Then I took 4 vectors.
$v_1$ having pair $(mnbal, bal)$ where $mnbal >= 0$ and $bal >= 0$
$v_2$ having pair $(mnbal, bal)$ where $mnbal < 0$ and $bal >= 0$
$v_4$ having pair $(mnbal, bal)$ where $mnbal < 0$ and $bal < 0$ and $mnbal = bal$
$v_3$ having pair $(mnbal, bal)$ where $mnbal < 0$ and $bal < 0$ and $mnbal \neq bal$

Then, I sorted $v2$ in decreasing order and $v3$ in increasing order, and appended $v_1$, $v_2$, $v_3$, $v_4$ in order checking conditions and it got accepted. But, I can't find out why my idea works.