← 返回题目列表

AtCoder · abc283_d

G. 范围

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

由小写英文字母组成的字符串, (,和 ) 据说是 好字符串 如果可以通过以下步骤将其设为空字符串:

  • 首先,删除所有小写英文字母。
  • 然后,重复删除连续的 () 虽然可能。

例如, ((a)ba) 是一个很好的字符串,因为删除所有小写英文字母会产生 (()),我们可以从中删除连续的 () 在 2-nd 和 3-rd 获取的字符 (),最终以空字符串结束。

你得到了一个很好的字符串 S。 我们表示为 S_i 这 i- 第一个字符 S.

对于每个小写英文字母 a, b, \ldots,和 z,我们有一个球,上面写着字母。 此外,我们还有一个空盒子。

对于每个 i = 1,2, \ldots ,|S| 按照这个顺序,高桥会执行以下操作,除非他晕倒。

  • If S_i 是一个小写英文字母,将写有字母的球放入盒子中。 如果球已经在盒子里,他就会晕倒。
  • If S_i is (,什么都不做。
  • If S_i is ),取最大整数 j 小于 i 这样 j-th 通过 i第一个字符 S 形成良好的字符串。 (我们可以证明这样一个整数 j 始终存在。)从盒子中取出他放入盒子中的所有球 j-th 通过 i第次操作。

确定高桥是否可以在不晕倒的情况下完成一系列操作。

约束

  • 1 \leq |S| \leq 3 \times 10^5
  • S 是一个很好的字符串。

输入

输入由标准输入按以下格式给出:

S

输出

打印 Yes 如果他能够完成一系列操作而不晕倒;打印 No 否则。


示例输入 1

((a)ba)

示例输出 1

Yes

对于 i = 1,他什么也没做。
对于 i = 2,他什么也没做。
对于 i = 3,他将球放在 盒子里写着 a 。
对于 i = 4, j=2 是小于的最大整数 4 这样 j-th 通过 4第一个字符 S 形成一个良好的线,所以他用 盒子上写着 a 。 上面写着
对于 i = 5,他将球放在 盒子里写着 b 。
对于 i = 6,他将球放在 盒子里写着 a 。
对于 i = 7, j=1 是小于的最大整数 7 这样 j-th 通过 7第一个字符 S 形成一个良好的线,所以他用 盒子上写着 a ,另一个写着 b,来自盒子。

因此,本例的答案是 Yes.


示例输入 2

(a(ba))

示例输出 2

No

对于 i = 1,他什么也没做。
对于 i = 2,他将球放在 盒子里写着 a 。
对于 i = 3,他什么也没做。
对于 i = 4,他将球放在 盒子里写着 b 。
对于 i = 5,球与 上面写的 a 已经在盒子里了,所以他晕了过去,中止了操作顺序。

因此,本例的答案是 No.


示例输入 3

(((())))

示例输出 3

Yes

示例输入 4

abca

示例输出 4

No