Community Problem
Remove Outermost Parentheses
Difficulty: Easy
Strip the outer parentheses of every primitive group in a balanced parenthesis string, in one pass with a depth counter.
Remove Outermost Parentheses
Strip the outer parentheses of every primitive group in a balanced parenthesis string, in one pass with a depth counter.
By @carlosherrera
March 24, 2026
·
Updated May 18, 2026
715 views
19
Rate
I keep this one in my warmup rotation because the depth-counter trick is the same idea that powers the harder Decode String and Score of Parentheses problems, but stripped down to a single integer of state. The version interviewers ask is always "do it in one pass without building any auxiliary structures".
Remove Outermost Parentheses
A balanced parenthesis string can be uniquely decomposed into a concatenation of primitive groups, where a primitive group is a non-empty balanced parenthesis string that cannot itself be split into two non-empty balanced parts. Given a balanced string s, return the string formed by concatenating all primitive groups after stripping their outermost pair of parentheses.
For example, "(()())(())" decomposes as "(()())" plus "(())". After stripping outer parens you get "()()" plus "()", concatenated to "()()()".
Examples
Example 1:
- Input:
s = "(()())(())" - Output:
"()()()" - Explanation: Primitives are
"(()())"and"(())". Strip the outer pair of each to get"()()"and"()", then concatenate.
Example 2:
- Input:
s = "(()())(())(()(()))" - Output:
"()()()()(())" - Explanation: Primitives are
"(()())","(())","(()(()))". After stripping:"()()","()","()(())".
Example 3:
- Input:
s = "()()" - Output:
"" - Explanation: Two primitives
"()"and"()", both strip to empty.
Example 4:
- Input:
s = "()" - Output:
"" - Explanation: One primitive that strips to empty.
Constraints
1 <= s.length <= 10^5s[i]is either'('or')'.sis a non-empty balanced parenthesis string.
Follow-up
Can you do it in one pass and O(n) total work, without using a stack of characters?
Solution
Hints
Approach
The primitives in a balanced string can be detected without an explicit stack: every time the running depth returns to zero you have just closed a primitive. Each primitive starts when depth goes from 0 to 1 (the outer opener) and ends when depth goes from 1 to 0 (the outer closer). All other parens are interior and should survive.
Key insight
Track a single integer depth. Before incrementing on '(', check whether depth > 0: if yes, this '(' is interior; if no, it is an outer opener. Symmetrically, after decrementing on ')', check whether depth > 0: if yes, the just-consumed ')' was interior; if no, it was an outer closer.
Algorithm
- Initialize an empty list of output characters and
depth = 0. - For each
chins:- If
ch == '(': append it to output ifdepth > 0, thendepth += 1. - If
ch == ')':depth -= 1, then append it to output ifdepth > 0.
- Join the output list into a string and return it.
Complexity
Metric Value
------ -----
Time O(n)
Space O(n) for the output buffer; O(1) extra besides the answerA single linear pass with constant work per character. The output buffer is bounded by n.
Why it works
A primitive group is a maximal balanced substring that touches zero depth only at its endpoints. The first character of any primitive is the only '(' that lifts depth from 0 to 1, and the last character is the only ')' that drops it back to 0. Skipping exactly those two events per primitive is equivalent to stripping the outer pair, and concatenating the surviving characters preserves the order.
Pitfalls
- Order matters: for
'('test BEFORE incrementing depth; for')'test AFTER decrementing. Swapping the order skips the wrong character. - Using
depth >= 1for the closer check is wrong because at the moment we see an outer closer,depthafter decrement is0, and we want to skip it. The check isdepth > 0. - Building the result with string concatenation
result += chisO(n^2)in some engines. Use an array of chars andjoin('')(JS) or alistand''.join(...)(Python).
Solution Code