No.3141 Balancing with X=>O Flip
Problem Statement
Definition of a balanced bracket sequence
A string $X$ is called a balanced bracket sequence if it satisfies the following.
- $X$ can be turned into the empty string by repeating, 0 or more times, the operation of deleting a
()contained in $X$ as a substring
For example, ()(()) and ()()()() are balanced bracket sequences, but ))(( and )()()( are not balanced bracket sequences.
There is a string $S$ of length $N$ consisting of ( and ).
Determine whether $S$ can be turned into a balanced bracket sequence by repeating the following operation any number of times, possibly 0.
- Replace a
)(contained in $S$ as a substring with(). More precisely, choose one $i(1\leq i\leq N - 1)$ satisfying $S_i=$), $S_{i+1}=$(, then replace $S_i$ with(and $S_{i+1}$ with)
Notation for strings
For a string $A$, let $|A|$ be the length of $A$. Then $A_i(1\leq i\leq |A|)$ denotes the $i$-th character of $A$.Input
$N$ $S$
- $1\leq N\leq 10^5$
- $S$ is a string of length $N$ consisting of
(,)
Output
Print Yes if $S$ can be turned into a balanced bracket sequence by 0 or more operations, and No otherwise.
Sample
Sample 1
Input
6 )))(((
Output
Yes
For example, performing the operations as )))((($\rightarrow$))()(($\rightarrow$)())(($\rightarrow$()))(($\rightarrow$())()($\rightarrow$()())($\rightarrow$()()() turns $S$ into a balanced bracket sequence.
Depending on the sequence of operations, other final forms such as (())() are also possible.
Sample 2
Input
5 ()()(
Output
No
It is impossible no matter how the operations are performed.
Sample 3
Input
8 )()()()(
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt