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

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

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()