Remove Outermost Parentheses — Editorial

Opening the reading…

Intuitiondepth identifies exactly which parentheses are outermost

A primitive starts when the nesting depth changes from 0 to 1 and ends when it changes from 1 to 0. Those two transitions identify its outermost opening and closing parentheses. Every parenthesis strictly between them belongs to the primitive's inside and must remain in the answer.

Scan the string from left to right while storing the depth before each character's effect is applied. For an opening parenthesis, copy it only if you are already inside a primitive, meaning the current depth is greater than 0. For a closing parenthesis, decrease the depth first, then copy it only if the new depth is still greater than 0. This removes exactly the two boundary characters without needing to split the string.

Approachone pass with the depth before and after each character

Create an empty result string and set depth to 0, because depth 0 means the scan is between primitive parts and no character there can belong to the answer.

For an opening parenthesis, check depth before incrementing it. Copy the character only when depth is greater than 0, because depth 0 identifies the primitive's outermost opening parenthesis.

Increment depth after handling the opening parenthesis, so it records the nesting level inside the newly opened pair for the next character.

For a closing parenthesis, decrement depth before deciding whether to copy it. If the new depth is 0, this is the primitive's outermost closing parenthesis and must be skipped.

Copy a closing parenthesis only when the depth after decrementing is greater than 0, because that means the closing parenthesis belongs to an inner pair.

Return the result after the scan. Every input character was considered once, and the valid-input guarantee means the depth returns to 0 at every primitive boundary.

Complexitythe scan uses constant working memory

MEASURE	BOUND	WHY
Time	O(n)	The loop processes each of the n characters exactly once, performing only constant-time comparisons, arithmetic, and at most one append per character, so no character is rescanned.
Space	O(1) extra	The depth counter uses constant working memory. The returned string is required output and is excluded from the space bound; the extra space remains O(1) regardless of how deeply or how many times the valid string is nested.

Here, n is the length of the input string.

Annotated solutionC++ · one pass · depth before and after each parenthesis

CPPA single depth counter removes each primitive's two outer boundary characters.

#include <string>
using namespace std;

class Solution {
public:
    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;
    }
};

The placement of the depth update is the central detail. An opening parenthesis is outermost when depth is 0 before the increment, so the code checks first and increments second. A closing parenthesis is outermost when depth becomes 0 after the decrement, so the code decrements first and checks second. These opposite orders make the two cases symmetric around the inside of each primitive.