对于一个合法的括号字符串我们需要满足两个条件,第一个是左括号与右括号数量相等,第二个是对与字符串的任意一个前缀左括号数量必须大于等于右括号数量,因为对于任意一个右括号都需要一个在它前面的左括号与之对应,所以寻找最长合法前缀只需要从前至后统计左括号与右括号的数量,当右括号数量大于左括号数量时所有之后的前缀便不合法,数量相等时便为一个合法前缀
#include <iostream>
#include <string>
using namespace std;
对于一个仅由左括号′(′和右括号′)′组成的字符串,小红想知道它的最长合法前缀的长度是多少。
对于某一个前缀,我们定义它是合法的,当且仅当该前缀满足以下条件:
存在一种拆分方案,可以将该前缀拆分为若干对匹配的括号′()′
如′()′,′()()′,′(())′都是合法的,而′)()(′,′))′是非法的。
特殊的,空串我们认为也是合法的。
第一行输入一个整数n,表示字符用的长度。
接下来一行输入一个长度为n的,仅由′(′和′)′组成的字符串。
1≤n≤105
输出一个整数,表示最长的合法前缀长度。
输入
5
(()))
输出
4
说明
可以证明前缀(())是最长且合法的前缀。