Remove Outermost Parentheses | Leetcode 1021 | Stack Depth Counting Solution

You are given a valid parentheses string s. Your task is to remove the outermost parentheses of every primitive substring.

• A primitive string is a non-empty valid parentheses string that cannot be split into two smaller non-empty valid parentheses strings.
• You need to return the final string after removing the outermost parentheses from each primitive.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "(()())(())"
Output: "()()()"
Explanation:
Primitive parts: "(()())" and "(())"
After removing outermost parentheses → "()()" + "()"
Final answer = "()()()"

Example 2

Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
Primitives: "(()())", "(())", "(()(()))"
After removing outermost → "()()", "()", "(())"
Final = "()()()()(())"

Example 3

Input: s = "()()"
Output: ""
Explanation:
Each primitive is "()" and removing the outer parentheses leaves nothing.

Intuition and Approach

The key idea is to track the nesting depth of parentheses:

1. Use a counter count to track how many open parentheses are currently active.
   • Increment count when you see '('.
   • Decrement count when you see ')'.
2. For each '(':
   • If count > 0, it means this '(' is not the outermost one, so add it to result.
   • Otherwise, skip it because it’s the outermost opening parenthesis of a primitive.
3. For each ')':
   • First decrement count.
   • If count > 0, it means this ')' is not the outermost one, so add it to result.
   • Otherwise, skip it because it’s the outermost closing parenthesis of a primitive.

By following this rule, the outermost parentheses of each primitive are excluded.

Code Implementation

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = ""
        count = 0
        for ch in s:
            if ch == "(":
                count += 1
                if count > 1:
                    result += ch
            else:
                count -= 1
                if count > 0:
                    result += ch
        return result

Code Explanation

• result: stores the final string after removing outermost parentheses.
• count: tracks the current nesting depth of parentheses.
• For every character:
  • If it’s '(': increase depth, add it only if depth is greater than 1.
  • If it’s ')': decrease depth, add it only if depth is still greater than 0 after decrement.
• This ensures that only inner parentheses are added, while outermost ones are skipped.

Dry Run

Input: s = "(()())(())"

Step by step:

• '(' → count = 1 → skip (outermost)
• '(' → count = 2 → add "("
• ')' → count = 1 → add ")"
• '(' → count = 2 → add "("
• ')' → count = 1 → add ")"
• ')' → count = 0 → skip (outermost closed)

First primitive processed → "()()".

Repeat for second primitive (()) → "()".

Final result: "()()()".

Time and Space Complexity

• Time Complexity: O(N) because we process each character once.
• Space Complexity: O(N) for the result string (ignoring input storage).

Conclusion

The Remove Outermost Parentheses problem can be solved neatly using a counter to track depth.
By skipping characters at depth 1 (outermost), we remove the unwanted parentheses and keep the inner structure intact.

This is a classic example of using nesting depth tracking instead of a full stack, making the solution both simple and efficient.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.