CF26B Regular Bracket Sequence
题目描述
给定一个只由左右圆括号构成的字符串 s,请你求出 s 的最长合法括号子序列的长度。
其中,子序列指从原字符串中删除任意个(可以为零个,也可以为全部)字符后得到的新字符串。
合法括号序列的定义如下:
∙空串是合法括号序列;
∙若 A 是合法括号序列,则 "(A)" 也是合法括号序列;
∙若 A 和 B 都是合法括号序列,则把 B 接在 A 之后得到的字符串 AB 也是合法括号序列。
换言之,从左到右扫描一个合法括号序列时,任意一个前缀中右括号的数量都不超过左括号的数量,并且整个序列中左右括号数量相等。
输入格式
输入一行一个字符串 s(1≦∣s∣≦106),保证 s 只由字符 ‘(’ 和 ‘)’ 构成。
输出格式
在一行上输出一个整数,代表 s 的最长合法括号子序列的长度。空串也是合法括号序列,因此答案总是存在;当 s 中不存在非空的合法括号子序列时,答案为 0。
测试样例
(()))(
4
样例 1 解释
字符串 s="(()))(" 的字符依次为 ‘(’、‘(’、‘)’、‘)’、‘)’、‘(’。
∙保留第 1,2,3,4 个字符,得到子序列 "(())",它是合法的括号序列,长度为 4;
∙第 5 个字符是 ‘)’,在它之前已经没有未被配对的 ‘(’,无法用它配对;
∙第 6 个字符是 ‘(’,在它之后已经没有 ‘)’,同样无法配对。
因此最多只能配成 2 对括号,最长合法括号子序列的长度为 4。
((()())
6