最长美观括号子序列问题

题目描述

达达是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。

这一天，刚刚起床的达达画了一排括号序列，其中包含小括号 ()、中括号 [] 和大括号 {}，总长度为 $N$。

这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的：

1. 空的括号序列是美观的；
2. 若括号序列 $A$ 是美观的，则括号序列 $(A)$、$[A]$、$\{A\}$ 也是美观的；
3. 若括号序列 $A$、$B$ 都是美观的，则括号序列 $AB$ 也是美观的。

例如 [(){}]() 是美观的括号序列，而 )({)[}]( 则不是。

现在达达想在她绘制的括号序列中，找出其中连续的一段，满足这段子串是美观的，并且长度尽量大。

你能帮帮她吗？

输入格式

输入一行由括号组成的字符串。

输出格式

输出一个整数，表示最长的美观的子段的长度。

输入输出样例

输入样例

({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)

输出样例

4

限制条件

• 字符串长度不超过 $10^5$

样例解释

在输入的字符串中，最长的美观括号子序列长度为 4。

可能的美观子序列如 ()、[]、{} 等，或者它们的组合如 ()[] 等。

问题分析

这是一个最长有效括号子序列问题，但括号类型有三种：()、[]、{}。

定义美观括号序列（即有效括号序列）：

1. 空串是有效的
2. 如果 A 是有效的，那么 (A)、[A]、{A} 也是有效的
3. 如果 A 和 B 都是有效的，那么 AB 也是有效的

我们需要找到最长的连续子串，使得它是一个有效的括号序列。

动态规划解法

设 dp[i] 表示以第 i 个字符结尾的最长有效括号子序列的长度。

状态转移：

1. 如果当前字符是右括号：)、]、}
2. 找到与之匹配的左括号位置：i - dp[i-1] - 1
3. 检查是否匹配：
   • s[i] == ')' 且 s[match] == '('
   • s[i] == ']' 且 s[match] == '['
   • s[i] == '}' 且 s[match] == '{'
4. 如果匹配，则 dp[i] = dp[i-1] + 2 + dp[match-1]（如果 match > 0）
5. 否则 dp[i] = 0

最终答案是 max(dp[i])。

算法步骤

1. 初始化 dp 数组全为 0
2. 遍历字符串的每个字符 i（从 1 开始）
3. 如果当前字符是右括号：
   • 计算匹配位置 match = i - dp[i-1] - 1
   • 如果 match >= 0 且字符匹配：
     • dp[i] = dp[i-1] + 2
     • 如果 match > 0：dp[i] += dp[match-1]
4. 更新最大长度
5. 输出最大长度

时间复杂度：$O(N)$ 空间复杂度：$O(N)$

示例

对于字符串 ()[]{}：

• dp[1] = 2（()）
• dp[3] = 2（[]）
• dp[5] = 2（{}）

对于字符串 (())：

• dp[1] = 2（()）
• dp[3] = 4（(())）：dp[2] = 0，match = 0，匹配成功，dp[3] = dp[2] + 2 + dp[-1]（越界视为 0）= 2

对于组合情况 ()[]：

• dp[1] = 2（()）
• dp[3] = 4（()[]）：match = 2，匹配成功，dp[3] = dp[2] + 2 + dp[1] = 0 + 2 + 2 = 4