Score : $400$ points

问题描述

一个由小写英文字母、( 和 ) 组成的字符串，如果可以通过以下过程变为一个空字符串，则称其为 好字符串：

• 首先，移除所有的小写英文字母。
• 然后，尽可能地重复移除连续的 ()。

例如，((a)ba) 是一个好字符串，因为移除所有小写英文字母后得到 (())，从这个字符串中我们可以在第 $2$ 个和第 $3$ 个字符位置移除连续的 () 得到 ()，最终得到空字符串。

给定一个好字符串 $S$。我们将 $S$ 的第 $i$ 个字符记为 $S_i$。

对于每个小写英文字母 a、b、$\ldots$、z，我们有一个上面写着该字母的球。另外，我们还有一个空盒子。

按照 $i = 1,2,$ $\ldots$ $,|S|$ 的顺序，Takahashi 会依次执行以下操作，除非他晕倒。

• 如果 $S_i$ 是一个小写英文字母，将写着该字母的球放入盒子中。如果该球已经存在于盒子里，那么他就会晕倒。
• 如果 $S_i$ 是 (，则不执行任何操作。
• 如果 $S_i$ 是 )，找到小于 $i$ 的最大整数 $j$，使得 $S$ 的第 $j$ 个到第 $i$ 个字符构成一个好字符串。（我们可以证明这样的整数 $j$ 总是存在的。）取出他在第 $j$ 次到第 $i$ 次操作中放入盒子的所有球。

确定 Takahashi 是否能够在不晕倒的情况下完成这一系列操作。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

A string consisting of lowercase English letters, (, and ) is said to be a good string if you can make it an empty string by the following procedure:

• First, remove all lowercase English letters.
• Then, repeatedly remove consecutive () while possible.

For example, ((a)ba) is a good string, because removing all lowercase English letters yields (()), from which we can remove consecutive () at the $2$-nd and $3$-rd characters to obtain (), which in turn ends up in an empty string.

You are given a good string $S$. We denote by $S_i$ the $i$-th character of $S$.

For each lowercase English letter a, b, $\ldots$, and z, we have a ball with the letter written on it. Additionally, we have an empty box.

For each $i = 1,2,$ $\ldots$ $,|S|$ in this order, Takahashi performs the following operation unless he faints.

• If $S_i$ is a lowercase English letter, put the ball with the letter written on it into the box. If the ball is already in the box, he faints.
• If $S_i$ is (, do nothing.
• If $S_i$ is ), take the maximum integer $j$ less than $i$ such that the $j$-th through $i$-th characters of $S$ form a good string. (We can prove that such an integer $j$ always exists.) Take out from the box all the balls that he has put in the $j$-th through $i$-th operations.

Determine if Takahashi can complete the sequence of operations without fainting.

Constraints

• $1 \leq |S| \leq 3 \times 10^5$
• $S$ is a good string.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print Yes if he can complete the sequence of operations without fainting; print No otherwise.

Sample Input 1

((a)ba)

Sample Output 1

Yes

For $i = 1$, he does nothing.
For $i = 2$, he does nothing.
For $i = 3$, he puts the ball with a written on it into the box.
For $i = 4$, $j=2$ is the maximum integer less than $4$ such that the $j$-th through $4$-th characters of $S$ form a good string, so he takes out the ball with a written on it from the box.
For $i = 5$, he puts the ball with b written on it into the box.
For $i = 6$, he puts the ball with a written on it into the box.
For $i = 7$, $j=1$ is the maximum integer less than $7$ such that the $j$-th through $7$-th characters of $S$ form a good string, so he takes out the ball with a written on it, and another with b, from the box.

Therefore, the answer to this case is Yes.

Sample Input 2

(a(ba))

Sample Output 2

No

For $i = 1$, he does nothing.
For $i = 2$, he puts the ball with a written on it into the box.
For $i = 3$, he does nothing.
For $i = 4$, he puts the ball with b written on it into the box.
For $i = 5$, the ball with a written on it is already in the box, so he faints, aborting the sequence of operations.

Therefore, the answer to this case is No.

Sample Input 3

(((())))

Sample Output 3

Yes

Sample Input 4

abca

Sample Output 4

No

update @ 2024/3/10 11:52:12