#P1956. 2024.8.28-DW-第3题-括号字符串

2024.8.28-DW-第3题-括号字符串

题目内容

对于一个仅由左括号′(′'('和右括号′)′')'组成的字符串，塔子哥想知道它的最长合法前缀的长度是多少。

对于某一个前缀，我们定义它是合法的，当且仅当该前缀满足以下条件：

存在一种拆分方案，可以将该前缀拆分为若干对匹配的括号′()′'()'

如′()′'()'，′()()′'()()'，′(())′'(())'都是合法的，而′)()(′')()('，′))′'))'是非法的。

特殊的，空串我们认为也是合法的。

输入描述

第一行输入一个整数nn，表示字符用的长度。

接下来一行输入一个长度为nn的，仅由′(′'('和′)′')'组成的字符串。

1≤n≤1051≤n≤10^5

输出描述

输出一个整数，表示最长的合法前缀长度。

示例1

输入

5
(()))

输出

4

说明

可以证明前缀(())(())是最长且合法的前缀。

知识点:*****

查看知识点以及同类型题目

Statistics