What is the primary pattern used to solve the Maximum Nesting Depth of Two Valid Parentheses Strings?

The primary pattern is stack-based state management, where the depth of parentheses is tracked using a stack.

What is the time complexity of the stack-based approach?

The time complexity is O(n), where n is the length of the string, as each character is processed once.

How can I handle invalid parentheses strings in this problem?

This problem assumes the input is always a valid parentheses string. Handling invalid strings would involve additional validation before processing the string.

What is the best data structure to track the nesting depth in this problem?

The stack is the best data structure for this problem as it allows for efficient tracking of the depth as you encounter each parenthesis.

How does GhostInterview help with solving this problem?

GhostInterview provides structured practice, detailed feedback, and hints to help you solve stack-based problems like this one effectively.

#1111

Medium

auto_awesome栈·状态

LeetCode 题解工作台

有效括号的嵌套深度

如果一个字符串仅由字符 "(" 和 ")" 组成，并且满足以下条件，则称为有效括号字符串（VPS）：它是空字符串，或它可以表示为 AB （ A 连接 B ），其中 A 和 B 都是VPS，或者它可以表示为 (A) ，其中 A 是一个 VPS。我们可以类似地定义任何 VPS S 的嵌套深度 d…

字符串栈

题目描述

如果一个字符串仅由字符 "(" 和 ")" 组成，并且满足以下条件，则称为有效括号字符串（VPS）：

它是空字符串，或
它可以表示为 AB（A 连接 B），其中 A 和 B 都是VPS，或者
它可以表示为 (A)，其中 A 是一个 VPS。

我们可以类似地定义任何 VPS S 的嵌套深度 depth(S) 如下：

depth("") = 0
depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 VPS
depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 VPS。

例如，""，"()()" 和 "()(()())" 都是 VPS（嵌套深度 0，1 和 2），并且 ")(" 和 "(()" 不是 VPS。

给定一个 VPS 序列，将其拆分成两个不相交的子序列 A 和 B，使得 A 和 B 都是 VPS（且 A.length + B.length = seq.length）。这些子序列不一定是连续的。

例如，对于序列 123456789，一种可能的拆分是：

A = {1, 3, 5, 7, 9}，
B = {2, 4, 6, 8}。
这对应于输出 [0, 1, 0, 1, 0, 1, 0, 1, 0]，其中 0 表示属于 A，1 表示属于 B。

现在选择任意这样的 A 和 B，使得 max(depth(A), depth(B)) 的值是最小的。

返回一个 answer 数组（长度为 seq.length），该数组编码了 A 和 B 的选择：如果 seq[i] 是 A 的一部分则 answer[i] = 0，否则 answer[i] = 1。请注意，尽管可能存在多种答案，但你可以返回其中任意一种。

示例 1：

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

示例 2：

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。

提示：

1 < seq.size <= 10000

有效括号字符串：

仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：

  1. 空字符串
  2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
  3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串

嵌套深度：

类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

  1. s 为空时，depth("") = 0
  2. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
  3. s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串

例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

lightbulb

解题思路

方法一：贪心

我们用一个变量 $x$ 维护当前括号的平衡度，也就是左括号的数量减去右括号的数量。

遍历字符串 $seq$ ，更新 $x$ 的值。如果 $x$ 为奇数，我们将当前的左括号分给 $A$ ，否则分给 $B$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $seq$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        ans = [0] * len(seq)
        x = 0
        for i, c in enumerate(seq):
            if c == "(":
                ans[i] = x & 1
                x += 1
            else:
                x -= 1
                ans[i] = x & 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate understands stack-based state management.
question_mark
Evaluate how well the candidate optimizes space and time complexity.
question_mark
Ensure the candidate handles edge cases like consecutive closing parentheses or unbalanced parentheses correctly.

warning

常见陷阱

外企场景

error
Forgetting to reset the depth value after encountering a closing parenthesis.
error
Incorrectly handling unbalanced parentheses strings.
error
Not accounting for deeply nested parentheses and overestimating depth at certain points.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing a solution without a stack, using a different data structure or approach.
arrow_right_alt
Allowing for invalid parentheses strings and handling errors or exceptions.
arrow_right_alt
Modifying the problem to return a boolean indicating if the parentheses are valid, instead of tracking depth.

help

常见问题

外企场景

继续练习

#1106 解析布尔表达式 #1096 花括号展开 II #1081 不同字符的最小子序列