AT_abc307_d [ABC307D] Mismatched Parentheses

题目描述

给定一个由小写英文字母以及 (、) 组成的长度为 $N$ 的字符串 $S$。
请重复执行如下操作，直到无法继续为止，并输出最终的 $S$。

• 可以任选 $S$ 的一个连续子串，要求该子串的第一个字符为 (，最后一个字符为 )，且除了首尾之外不包含任何 ( 或 )，然后将这个子串删除。

可以证明，无论操作顺序如何，最终得到的 $S$ 是唯一的。

输入格式

输入以以下格式从标准输入给出。

$N$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

8
a(b(d))c

输出 #1

ac

输入输出样例 #2

输入 #2

5
a(b)(

输出 #2

a(

输入输出样例 #3

输入 #3

2
()

输出 #3

输入输出样例 #4

输入 #4

6
)))(((

输出 #4

)))(((

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $N$ 是整数
• $S$ 是由小写英文字母和 (、) 组成的长度为 $N$ 的字符串

样例解释 1

例如，可以按如下步骤操作，最终 $S$ 变为 ac。

• 删除 $S$ 的第 $4$ 个到第 $6$ 个字符组成的子串 (d)，此时 $S$ 变为 a(b)c。
• 删除 $S$ 的第 $2$ 个到第 $4$ 个字符组成的子串 (b)，此时 $S$ 变为 ac。
• 此时无法再进行操作。

样例解释 3

最终的 $S$ 可能为空字符串。

由 ChatGPT 4.1 翻译