M29952: 咒语序列

stack, http://cs101.openjudge.cn/practice/29952/

在高等精灵的魔法体系中，一个强大的咒语通常由一连串的基础符文构成。这些符文分为三种类型，并以配对的形式出现：()、[] 和 {}。

一个咒语序列被认为是“和谐的”，当且仅当它满足：任何一个开启符文（(、[、{）都必须有一个与之对应的关闭符文（)、]、}），且必须先开启再关闭。显然，在一类符文配对前，可以插入其他类型的符文而不影响最终的“和谐”。

例如 "{[]}" 是和谐的，但 "{[)]}" 和 "{[}" 都不是。

在基础的咒语和谐判断之上，高阶法师们研究起了“部分和谐”的咒语。一个咒语序列可能整体上不和谐，但它内部可能包含一个或多个“和谐的”子串。注意，子串必须是原咒语序列中若干个连续的符文。

例如，咒语 ()(() 整体不和谐，但它包含和谐的子串 ()（长度2）和 ()（长度2）。而咒语 )((())))(中，最长的和谐子串是 ((()))，长度为 6。

现在，给定一个只包含 ( 和 ) 的咒语序列，请你找出其中最长的和谐子串的长度。

输入

一行，一个只包含 ( 和 ) 的字符串，长度不超过 30000。

输出

输出一个整数，代表最长和谐子串的长度。

样例输入

)((()))((()

样例输出

提示

tag: stack

来源

2025 TA-lxy

python

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]  # 初始化栈，存放“上一个无效位置”的下标
    max_len = 0

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # 栈空了，说明这一段结束，更新新的无效起点
                stack.append(i)
            else:
                # 有效匹配，更新最长长度
                max_len = max(max_len, i - stack[-1])

    return max_len


# 读取输入并输出
if __name__ == "__main__":
    s = input().strip()
    print(longest_valid_parentheses(s))

M29952: 咒语序列 ​

M29952: 咒语序列