Remove Outermost Parentheses

easy stack string depth counter

Problem

A valid parentheses string is either empty, "(" + A + ")" where A is valid, or A + B where A and B are valid. A valid string s can be split into primitive pieces. Remove the outermost parentheses of every primitive piece of s and return the resulting string.

Inputs = "(()())(())"

Output"()()()"

The primitives are "(()())" and "(())". Stripping their outer pair gives "()()" and "()", concatenated to "()()()".

s (parentheses only)

def remove_outer_parentheses(s):
    res = []
    depth = 0
    for c in s:
        if c == '(':
            if depth > 0:
                res.append(c)
            depth += 1
        else:
            depth -= 1
            if depth > 0:
                res.append(c)
    return ''.join(res)

function removeOuterParentheses(s) {
  let res = "";
  let depth = 0;
  for (const c of s) {
    if (c === '(') {
      if (depth > 0) res += c;
      depth++;
    } else {
      depth--;
      if (depth > 0) res += c;
    }
  }
  return res;
}

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder res = new StringBuilder();
        int depth = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (depth > 0) res.append(c);
                depth++;
            } else {
                depth--;
                if (depth > 0) res.append(c);
            }
        }
        return res.toString();
    }
}

string removeOuterParentheses(string s) {
    string res;
    int depth = 0;
    for (char c : s) {
        if (c == '(') {
            if (depth > 0) res += c;
            depth++;
        } else {
            depth--;
            if (depth > 0) res += c;
        }
    }
    return res;
}

Explanation

We need to drop only the outermost pair of parentheses of each primitive piece while keeping all the inner ones. Instead of actually splitting the string into pieces, we use a single counter called depth that tracks how deeply nested we currently are.

The key insight: a parenthesis is "outermost" exactly when it sits at depth 0. So as we scan, an opening ( is kept only if depth > 0 (we are already inside something), and a closing ) is kept only if it leaves us still inside, i.e. depth stays above 0 after decrementing.

The ordering matters. For ( we test depth first, then increment. For ) we decrement first, then test. This way the ( that opens a primitive (seen at depth 0) and the ) that closes it (bringing depth back to 0) are both dropped.

Example: s = "(()())(())". The very first ( is at depth 0 → dropped, depth becomes 1. The next chars are inner and kept until depth returns to 0 at the matching ), which is dropped. The first primitive contributes "()()", the second "()", giving "()()()".

Because we only ever read each character once and adjust a single counter, the whole thing runs in one clean pass.

Time: O(n) Space: O(n)