平衡括号的最长“子序列”

Question

我正在尝试解决我之前问过的一个问题的变体：

给定一串括号（长度 <= 1,000,000）和范围查询列表，为 <= 100,000 查询中的每一个查询在每个范围内找到平衡括号的最长子序列

我发现了另一个类似的问题，但只有一个 O(N^3) 算法。

我相信这种形式的 DP 解决方案dp[i, j] = longest balanced subsequence in [i .. j]应该可以工作，因为一旦计算，这将能够仅通过查询 DP 表来回答所有范围查询。然而，由于可能的输入字符串长度很大，即使是这个问题的 O(N^2) 解决方案也会超过时间限制。

此外，使用堆栈跟踪匹配括号的技巧不再直接有效，因为您正在寻找子序列，而不是子字符串。

我有一种我认为可能有效但不确定的方法：

一个区间内平衡括号的最长子序列的长度是该区间内平衡括号的最长非重叠子串的长度之和。

例如，如果您有字符串

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

) ) ( ( ) ( ( ) ) ) ) ( ( ) )

区间[0, 8]（含）内平衡括号的最长子序列长度为5，该长度等于区间内最长非重叠子串的长度之和：“( )” + "( ( ) )"。

这种方法会一直有效，还是有更好的方法？

Answer 1

由于其他人发布了答案，这里是O(n)对带有O(1)空格的单个查询的答案。保持括号的计数平衡并指向最后一个打开和最后一个关闭的括号。直到你用完字符串，在最后一次打开时向前扫描以找到另一个打开的括号。然后从最后一个打开和最后一个关闭的括号的最大值向前扫描以找到下一个关闭的括号。如果您以这种方式找到一对，请增加平衡的括号计数。当您到达字符串的末尾时，您将获得正确的计数，即使您错误地配对了括号。

实际上可能有多个平衡括号的最大子序列。但是，如果您采用平衡括号的任何最大子序列，并将每个开放括号替换为最左侧可能的开放括号，然后将每个闭合括号替换为最左侧可能的开放括号，结果将是您找到的结果。（证明留给读者作为一个有启发性的练习。）

这里是伪代码。

parens = 0
last_open = 0
last_closed = 0
while last_open < len(str) && last_closed < len(str):
    if str[last_open] == ')':
        # We are looking for the next open paren.
       last_open += 1
    elif last_closed < last_open:
       # Start our search for a last closed after the current char
       last_closed = last_open + 1
    elif str[last_closed] == '(':
       # still looking for a close pair
       last_closed += 1
    else:
       # We found a matching pair.
       parens += 1
       last_open += 1
# and now parens has the correct answer.

接下来我们面临许多范围查询的挑战。事实证明，要做到这一点需要O(n)预先计算和O(n)空间，并且每个范围查询都需要O(log(n))时间。

这是该问题的提示。假设我们有两个相邻的块 A 和 B。每个内部都有一定数量的平衡子序列，右侧有一些额外的开放括号，左侧有一些额外的关闭括号。那么组合块C具有以下内容：

C.balanced = A.balanced + B.balanced + min(A.open, B.close)
C.open = B.open + max(A.open - B.close, 0)
C.close = A.close + max(B.close - A.open, 0)

我让您自行确定要预先计算哪些块集以便能够及时计算任何块O(log(n))。