LeetCode 1021: Remove Outermost Parentheses

Problem Restatement

A valid parentheses string is either empty, a concatenation of valid strings, or a valid string wrapped in parentheses.

A primitive valid parentheses string is one that cannot be split into two non-empty valid strings.

We are given a valid parentheses string s.

We need to remove the outermost parentheses of every primitive part in s and return the result.

The official constraints state that 1 <= s.length <= 10^5 and s consists of ( and ).

Input and Output

Item	Meaning
Input	Valid parentheses string s
Output	s with outermost parentheses of each primitive removed

Function shape:

def removeOuterParentheses(s: str) -> str:
    ...

Examples

Example 1:

s = "(()())(())"

Primitives: "(()())" and "(())".

After removing outer: "()()" and "()".

Answer:

"()()()"

Example 2:

s = "(()())(())(()(()))"

Primitives: "(()())", "(())", "(()(()))".

After removing outer: "()()", "()", "()(())".

Answer:

"()()()()(())"

Example 3:

s = "()()"

Primitives: "()" and "()".

After removing outer: "" and "".

Answer:

""

Key Insight

Track the nesting depth as we scan the string.

A ( at depth 0 starts a new primitive (it is the outermost (). Don't include it.

A ) that brings depth back to 0 ends a primitive (it is the outermost )). Don't include it.

All other characters (at depth > 0 before update) are interior and should be included.

Algorithm

1. Initialize depth = 0 and an empty result list.
2. For each character c in s:
   • If c == '(':
     • If depth > 0, append c to result (not the outermost).
     • Increment depth.
   • If c == ')':
     • Decrement depth.
     • If depth > 0, append c to result (not the outermost).
3. Return the joined result.

Correctness

Opening parentheses at depth 0 are outermost openers of primitives. By checking depth > 0 before appending, we skip them.

Closing parentheses that bring depth to 0 are outermost closers of primitives. By checking depth > 0 after decrement, we skip them.

All other characters are interior and correctly included.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Complexity

Metric	Value	Why
Time	O(n)	Single pass
Space	O(n)	Result array

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

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

        return "".join(result)

Code Explanation

For (:

if depth > 0:
    result.append(c)
depth += 1

We append only if we are already inside a primitive (depth > 0). Then increase depth.

For ):

depth -= 1
if depth > 0:
    result.append(c)

We decrease depth first. If depth is still > 0, this is an interior ).

Testing

def run_tests():
    s = Solution()

    assert s.removeOuterParentheses("(()())(())") == "()()()"
    assert s.removeOuterParentheses("(()())(())(()(()))") == "()()()()(())"
    assert s.removeOuterParentheses("()()") == ""
    assert s.removeOuterParentheses("((()))") == "(())"

    print("all tests passed")

run_tests()

Test	Expected	Why
"(()())(())"	"()()()"	Two primitives stripped
"(()())(())(()(()))"	"()()()()(())"	Three primitives stripped
"()()"	""	Two trivial primitives
"((()))"	"(())"	Single nested primitive