How do I handle nested parentheses in the Remove Outermost Parentheses problem?

Use a stack to track the opening and closing parentheses, adjusting the string based on the nesting depth to identify outermost parentheses.

What is the time complexity of solving the Remove Outermost Parentheses problem?

The time complexity is O(n), where n is the length of the input string, since we process each character once.

Can I solve the Remove Outermost Parentheses problem recursively?

Yes, recursion can be used, but it may not be as efficient as the stack-based approach for large input strings.

What is the primary pattern for solving the Remove Outermost Parentheses problem?

The primary pattern involves stack-based state management, where you track the depth of the parentheses to remove outermost layers.

What is meant by a primitive decomposition of a parentheses string?

Primitive decomposition refers to splitting the string into components where each part cannot be further divided into smaller valid parentheses strings.

#1021

Easy

auto_awesome栈·状态

LeetCode 题解工作台

删除最外层的括号

有效括号字符串为空 "" 、 "(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串， + 代表字符串的连接。例如， "" ， "()" ， "(())()" 和 "(()(()))" 都是有效的括号字符串。如果有效字符串 s 非空，且不存在将其拆分为 s = A …

字符串栈

题目描述

有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

示例 1：

输入：s = "(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入：s = "(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入：s = "()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

1 <= s.length <= 10⁵
s[i] 为 '(' 或 ')'
s 是一个有效括号字符串

lightbulb

解题思路

方法一：计数

遍历字符串，遇到左括号 '(' 计数器加一，此时计数器不为 $1$ 时，说明当前括号不是最外层括号，将其加入结果字符串。遇到右括号 ')' 计数器减一，此时计数器不为 $0$ 时，说明当前括号不是最外层括号，将其加入结果字符串。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串长度。忽略答案字符串的空间开销，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
                if cnt > 1:
                    ans.append(c)
            else:
                cnt -= 1
                if cnt > 0:
                    ans.append(c)
        return ''.join(ans)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate efficiently manages state using a stack to handle nested structures.
question_mark
The candidate demonstrates an understanding of primitive decomposition and how to handle nested parentheses.
question_mark
The candidate optimizes the solution to process the string in linear time, demonstrating awareness of algorithm efficiency.

warning

常见陷阱

外企场景

error
Incorrectly handling nested parentheses, leading to the removal of incorrect parentheses.
error
Not accounting for strings that are already fully decomposed, resulting in an incorrect output.
error
Using inefficient solutions, such as multiple passes through the string, which can cause unnecessary performance overhead.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the input string contains only a single primitive substring with no nesting?
arrow_right_alt
What if the parentheses are non-nested but the string is long?
arrow_right_alt
Can this problem be solved using recursion instead of a stack?

help

常见问题

外企场景

继续练习

#1003 检查替换后的词是否有效 #1047 删除字符串中的所有相邻重复项 #1081 不同字符的最小子序列