Problem statement

Given a string sequence consisting of length $N$ only of opening or closing parentheses ( ) [ ] { }, determine if the sequence is a correct bracket sequence.

For example: If $s1$ and $s2$ are correct bracket sequences, so are the following:

• $(s1)s2$
• $(s1 s2)$
• $[(\{s1\}s2)]$

But these are not:

• $)s1s2)$
• $[s1)s2$

Sample

Input:

[()]{}{[()()]()}

Output:

Yes

Constraints:

$1<=N<=10^6$

Brute force

Obviously, if it’s a balanced sequence, every opening bracket, ( [ {, is matched to exactly one closing bracket, ) ] }, of the same type.

We can parse to look for every closing bracket and try to find its corresponding opening bracket in the string parsed so far.

It would be the first opening bracket to its left that didn’t match up with any bracket yet. So, you keep track of matched brackets as well.

If we are able to match all the brackets, then it’s a balanced sequence, otherwise it’s not. See the illustration below for a better understanding: