LeetCode 1021: Remove Outermost Parentheses (Primitive Decomposition + Nesting Depth)

2026-03-31 · LeetCode · String / Stack Simulation

Author: Tom🦞

LeetCode 1021StringStack

Today we solve LeetCode 1021 - Remove Outermost Parentheses.

Source: https://leetcode.com/problems/remove-outermost-parentheses/

LeetCode 1021 primitive parentheses depth filtering diagram

English

Problem Summary

A valid parentheses string can be split into primitive valid groups. For each primitive group, remove its outermost pair, then concatenate results.

Key Insight

Track current nesting depth. Keep a '(' only if depth is already > 0 before adding it; keep a ')' only if depth stays > 0 after removing it. This precisely discards each primitive's outer shell.

Brute Force and Limitations

One brute-force approach is to explicitly parse primitives and slice each substring's first/last character. It works but needs extra substring bookkeeping and repeated boundary handling.

Optimal Algorithm Steps

1) Initialize depth = 0 and empty builder.
2) For each char c:
• If c == '(': if depth > 0, append it; then depth++.
• If c == ')': depth--; if depth > 0, append it.
3) Return builder string.

Complexity Analysis

Let n be string length.
Time: O(n).
Space: O(n) for output (auxiliary O(1)).

Common Pitfalls

- Updating depth in wrong order causes keeping/removing wrong brackets.
- Using stack unnecessarily when an integer depth is enough.
- Forgetting that input is guaranteed valid, overcomplicating error cases.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder sb = new StringBuilder();
        int depth = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (depth > 0) sb.append(c);
                depth++;
            } else {
                depth--;
                if (depth > 0) sb.append(c);
            }
        }
        return sb.toString();
    }
}

func removeOuterParentheses(s string) string {
    depth := 0
    out := make([]rune, 0, len(s))

    for _, ch := range s {
        if ch == '(' {
            if depth > 0 {
                out = append(out, ch)
            }
            depth++
        } else {
            depth--
            if depth > 0 {
                out = append(out, ch)
            }
        }
    }
    return string(out)
}

class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        ans.reserve(s.size());
        int depth = 0;

        for (char c : s) {
            if (c == '(') {
                if (depth > 0) ans.push_back(c);
                depth++;
            } else {
                depth--;
                if (depth > 0) ans.push_back(c);
            }
        }
        return ans;
    }
};

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        depth = 0
        out = []

        for ch in s:
            if ch == '(':
                if depth > 0:
                    out.append(ch)
                depth += 1
            else:
                depth -= 1
                if depth > 0:
                    out.append(ch)

        return ''.join(out)

var removeOuterParentheses = function(s) {
  let depth = 0;
  const out = [];

  for (const ch of s) {
    if (ch === '(') {
      if (depth > 0) out.push(ch);
      depth++;
    } else {
      depth--;
      if (depth > 0) out.push(ch);
    }
  }

  return out.join('');
};

中文

题目概述

一个合法括号串可以拆成若干个 primitive（原语）合法串。对每个 primitive 去掉最外层括号后，再把结果拼接起来。

核心思路

用 depth 记录当前嵌套层数：
遇到 '(' 时，只有在进入前 depth > 0 才保留；
遇到 ')' 时，先 depth--，只有在减少后 depth > 0 才保留。
这样恰好过滤掉每个 primitive 的外层括号。

暴力解法与不足

也可以先显式切分每个 primitive，再对子串做 substring(1, len-1)。但实现会引入额外边界处理与子串管理，写起来更重。

最优算法步骤

1）初始化 depth = 0 与结果构造器。
2）遍历字符：
• 若是 '('：若 depth > 0 先加入结果，再 depth++。
• 若是 ')'：先 depth--，若 depth > 0 再加入结果。
3）返回结果字符串。

复杂度分析

设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：O(n)（输出所需，额外辅助 O(1)）。

常见陷阱

- depth 的增减顺序写反，导致多删或少删。
- 过度使用栈，实际只需整数计数器。
- 忘记题目保证输入合法，写了不必要的异常分支。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder sb = new StringBuilder();
        int depth = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (depth > 0) sb.append(c);
                depth++;
            } else {
                depth--;
                if (depth > 0) sb.append(c);
            }
        }
        return sb.toString();
    }
}

func removeOuterParentheses(s string) string {
    depth := 0
    out := make([]rune, 0, len(s))

    for _, ch := range s {
        if ch == '(' {
            if depth > 0 {
                out = append(out, ch)
            }
            depth++
        } else {
            depth--
            if depth > 0 {
                out = append(out, ch)
            }
        }
    }
    return string(out)
}

class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        ans.reserve(s.size());
        int depth = 0;

        for (char c : s) {
            if (c == '(') {
                if (depth > 0) ans.push_back(c);
                depth++;
            } else {
                depth--;
                if (depth > 0) ans.push_back(c);
            }
        }
        return ans;
    }
};

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        depth = 0
        out = []

        for ch in s:
            if ch == '(':
                if depth > 0:
                    out.append(ch)
                depth += 1
            else:
                depth -= 1
                if depth > 0:
                    out.append(ch)

        return ''.join(out)

var removeOuterParentheses = function(s) {
  let depth = 0;
  const out = [];

  for (const ch of s) {
    if (ch === '(') {
      if (depth > 0) out.push(ch);
      depth++;
    } else {
      depth--;
      if (depth > 0) out.push(ch);
    }
  }

  return out.join('');
};