#CF26B. 最长合法括号子序列

最长合法括号子序列

CF26B Regular Bracket Sequence

题目描述

\hspace{15pt}给定一个只由左右圆括号构成的字符串 ss,请你求出 ss 的最长合法括号子序列的长度。

\hspace{15pt}其中,子序列指从原字符串中删除任意个(可以为零个,也可以为全部)字符后得到的新字符串。

\hspace{15pt}合法括号序列的定义如下:

∙ \hspace{23pt}\bullet\,空串是合法括号序列;

∙ \hspace{23pt}\bullet\,若 AA 是合法括号序列,则 "(A)"\texttt{"(}A\texttt{)"} 也是合法括号序列;

∙ \hspace{23pt}\bullet\,若 AA 和 BB 都是合法括号序列,则把 BB 接在 AA 之后得到的字符串 ABAB 也是合法括号序列。

\hspace{15pt}换言之,从左到右扫描一个合法括号序列时,任意一个前缀中右括号的数量都不超过左括号的数量,并且整个序列中左右括号数量相等。

输入格式

\hspace{15pt}输入一行一个字符串 s(1≦∣s∣≦106)s \left(1 \leqq |s| \leqq 10^6\right),保证 ss 只由字符 ‘(’\texttt{`('} 和 ‘)’\texttt{`)'} 构成。

输出格式

\hspace{15pt}在一行上输出一个整数,代表 ss 的最长合法括号子序列的长度。空串也是合法括号序列,因此答案总是存在;当 ss 中不存在非空的合法括号子序列时,答案为 00。

测试样例

(()))(
4

样例 1 解释

\hspace{15pt}字符串 s="(()))("s=\texttt{"(()))("} 的字符依次为 ‘(’\texttt{`('}、‘(’\texttt{`('}、‘)’\texttt{`)'}、‘)’\texttt{`)'}、‘)’\texttt{`)'}、‘(’\texttt{`('}。

∙ \hspace{23pt}\bullet\,保留第 1,2,3,41,2,3,4 个字符,得到子序列 "(())"\texttt{"(())"},它是合法的括号序列,长度为 44;

∙ \hspace{23pt}\bullet\,第 55 个字符是 ‘)’\texttt{`)'},在它之前已经没有未被配对的 ‘(’\texttt{`('},无法用它配对;

∙ \hspace{23pt}\bullet\,第 66 个字符是 ‘(’\texttt{`('},在它之后已经没有 ‘)’\texttt{`)'},同样无法配对。

\hspace{15pt}因此最多只能配成 22 对括号,最长合法括号子序列的长度为 44。

((()())
6