Remove Outermost Parentheses

Problem Link

1021. Remove Outermost Parentheses – LeetCode

Problem Statement

Given a valid parentheses string s, return a new string after removing the outermost parentheses of every primitive substring.

Definitions:

• A valid parentheses string is either:

  • "()" (simple pair)

  • "(" + A + ")" where A is valid

  • "A + B" where A and B are valid

• A primitive valid parentheses string is:

  • Non-empty

  • Cannot be split into two non-empty valid parentheses strings

Objective:

Decompose s into its primitive components P1 + P2 + ... + Pk, and for each primitive, remove its outermost parentheses.

Examples

Example 1:

Input: s = "(()())(())"
Primitive parts: "(()())", "(())"
After removing outermost: "()()", "()"
Output: "()()()"

Example 2:

Input: s = "(()())(())(()(()))"
Primitive parts: "(()())", "(())", "(()(()))"
After removing outermost: "()()", "()", "()(())"
Output: "()()()()(())"

Example 3:

Input: s = "()()"
Primitive parts: "()", "()"
After removing outermost: "", ""
Output: ""

Constraints

• 1 <= s.length <= 10⁵

• s[i] is either '(' or ')'

• s is a valid parentheses string

Intuition

We are asked to strip the outermost parentheses from each primitive, not just from the entire string.

To identify a primitive:

• Start tracking depth with a counter

• Every time depth goes from 0 → 1, you're at the start of a new primitive

• When depth drops back to 0, you’ve finished that primitive

Now, while traversing:

• If depth > 1: include '(' (not outermost)

• If depth < max: include ')' (not outermost)

Approach

1. Use a counter depth to track current level of nesting.

2. Traverse the string:

   • For '(': if depth > 0, it's not outermost → append; then increment depth

   • For ')': decrement depth first; if depth > 0, it's not outermost → append

3. The first '(' and last ')' of a primitive are skipped by using the depth check.

Java Code

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

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

        return sb.toString();
    }
}

Time and Space Complexity

• We traverse each character once.

• Output string builder may hold up to n characters.

Dry Run

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

Initial: depth = 0

i=0, ch='(' → depth=1 → skip (outermost)
i=1, ch='(' → depth=2 → append '('
i=2, ch=')' → depth=1 → append ')'
i=3, ch='(' → depth=2 → append '('
i=4, ch=')' → depth=1 → append ')'
i=5, ch=')' → depth=0 → skip (outermost)

→ primitive1: "()()"

Repeat for second primitive:
i=6 to i=10 → append "()"

Final output: `"()()()"`

Conclusion

This problem teaches:

• Tracking depth in parentheses parsing

• Detecting primitive valid substrings

• Efficiently removing the outer layer of nesting

A classic use-case of stack-like logic without an actual stack, optimized using just a counter (depth).