Remove Outermost Parentheses: When a Counter Beats the Stack
Solve Remove Outermost Parentheses in O(n) with a depth counter instead of a stack — intuition, JavaScript code, a full walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Remove Outermost Parentheses looks like a stack problem, gets filed under stack problems, and appears in every stack study list. Then you solve it properly and realize the punchline: you never push a single character. The only thing a stack would tell you here is how tall it is — so you replace the whole data structure with one integer.
That replacement has a name — depth counting — and it's worth learning as a pattern, not a one-off trick. A surprising number of "stack" problems only ever consult the stack's size, and every one of them collapses into a counter the same way.
The problem also teaches precision about when you update state: the whole solution hangs on two ordering decisions, and flipping either one silently produces wrong answers.
The problem
A valid parentheses string is primitive if it's nonempty and cannot be split into two nonempty valid parentheses strings. Every valid string has a unique decomposition into primitives: "(()())(())" splits into "(()())" and "(())", and no other split works.
Given a valid parentheses string s, remove the outermost parentheses of every primitive in its decomposition and return the result.
Input: s = "(()())(())"
Primitives: (()()) + (())
Strip shells: ()() + ()
Output: "()()()"Two guarantees in the statement do a lot of quiet work:
- The input is always valid, so the running nesting depth never goes negative and always ends at 0. No validation code needed.
- Only round parentheses appear — one bracket type. That's exactly the condition that lets a counter stand in for a stack.
The brute force baseline
The literal reading of the problem suggests a two-phase plan: first find the primitive boundaries, then strip the first and last character of each piece.
function removeOuterParentheses(s) {
const primitives = [];
let balance = 0;
let start = 0;
// Phase 1: split into primitives
for (let i = 0; i < s.length; i++) {
balance += s[i] === '(' ? 1 : -1;
if (balance === 0) { // a primitive just closed
primitives.push(s.slice(start, i + 1));
start = i + 1;
}
}
// Phase 2: strip each shell
return primitives.map(p => p.slice(1, -1)).join('');
}This is already O(n) time — there's no asymptotic villain to defeat in this problem. What's wrong with it is everything else: two passes over the data, an intermediate array of substrings (each slice allocates a copy, so every character gets touched three times), and three pieces of index bookkeeping that each host an off-by-one bug waiting to happen.
The other tempting baseline is a literal stack — push each (, pop on ), and treat the moments the stack becomes empty as shell boundaries. It works, but notice what you actually read from that stack: never its contents, only its length. You're paying O(n) memory to store characters you already know are all '('.
The key insight: depth is the only state you need
Reframe the question per character instead of per primitive: should this character survive?
Track depth — the current nesting level. A character is part of an outermost shell exactly when it touches depth 0:
- A
(read at depth 0 opens a new primitive. It's a shell bracket — discard it. - A
)that brings depth back to 0 closes that primitive. Also shell — discard. - Everything else lives at depth ≥ 1 inside some primitive — keep it.
That's the whole algorithm. No splitting, no substrings, no stack. One integer summarizes everything the stack would have told you, because with a single bracket type and guaranteed-valid input, the stack's contents carry zero information beyond its height.
The subtlety is when you compare against zero, and it differs by bracket direction:
- For
(: checkdepth > 0before incrementing. The shell(sees depth 0 and gets skipped; only then does depth rise to 1. - For
): decrement before checkingdepth > 0. The shell)drags depth down to 0 and gets skipped; an inner)lands at 1 or higher and survives.
Both rules exist so the same test — depth > 0 — means "this character is strictly inside a primitive" in both cases.
The optimal solution
This is the exact algorithm the visualizer steps through:
function removeOuterParentheses(s) {
let output = '';
let depth = 0;
for (const ch of s) {
if (ch === '(') {
if (depth > 0) output += ch;
depth++;
} else {
depth--;
if (depth > 0) output += ch;
}
}
return output;
}Eleven lines, one pass, one counter. The asymmetry between the two branches — append-then-increment versus decrement-then-append — is the solution; everything else is a loop.
To watch the skip/copy decision fire on every character, step through it interactively — each bracket is colored copied or skipped as the depth meter moves.
Walkthrough: s = "(())()"
Two primitives: "(())" (which contributes "()") and "()" (which contributes nothing — it's all shell).
| Step | ch | depth before | Decision | depth after | output |
|---|---|---|---|---|---|
| 1 | ( | 0 | depth is 0 → skip (shell opens) | 1 | "" |
| 2 | ( | 1 | depth > 0 → copy | 2 | "(" |
| 3 | ) | 2 | decrement to 1, still > 0 → copy | 1 | "()" |
| 4 | ) | 1 | decrement to 0 → skip (shell closes) | 0 | "()" |
| 5 | ( | 0 | depth is 0 → skip (new shell opens) | 1 | "()" |
| 6 | ) | 1 | decrement to 0 → skip (shell closes) | 0 | "()" |
Result: "()". Steps 5–6 are the instructive ones: the primitive "()" is nothing but shell, so stripping it leaves the empty string. Depth returning to 0 at steps 4 and 6 is exactly where the primitive boundaries sit — the counter rediscovers the decomposition for free, without ever materializing it.
Complexity
| Approach | Time | Extra space | Why |
|---|---|---|---|
| Split into primitives, strip each | O(n) | O(n) | intermediate substring copies of nearly the whole input |
| Literal stack | O(n) | O(n) | stores every open bracket, but only the count is ever read |
| Depth counter | O(n) | O(1) | one integer of working state; single pass |
All three produce an output string of up to n − 2 characters, which any solution must — so "extra space" here means working memory beyond the answer. The depth counter is the only version that needs none.
Common mistakes
- Flipping the update order on
(. If you increment before checking, the shell(sees depth 1 and gets copied. Every primitive keeps its opening bracket and the output is unbalanced garbage. - Flipping the check order on
). If you test before decrementing, the shell)sees depth 1 and survives. Same class of bug, mirror image. - Splitting into primitives first. It works, but it triples the character touches, allocates throwaway substrings, and adds boundary-index bookkeeping — three bug surfaces the single pass simply doesn't have.
- Reaching for a real stack. Not wrong, just wasteful. When you notice you only ever call the equivalent of
stack.length, that's the signal to swap in a counter. - Building the string naively in other languages. JavaScript engines optimize
output += chwell, but in Java use aStringBuilderand in Python collect characters into a list and''.join(...)— repeated immutable-string concatenation degrades to O(n²).
Where this pattern shows up next
Depth counting is the first stop in a broader theme: understanding what a stack or queue is really doing for you, and when a cheaper stand-in suffices.
- Valid Parentheses — the sibling problem where a counter is not enough: with three bracket types you must remember which opener is pending, so a real stack returns.
- Implement Stack using Queues — building LIFO behavior out of FIFO parts, forcing you to articulate exactly what each structure guarantees.
- Implement Queue using Stacks — the reverse construction, with a beautiful amortized O(1) analysis.
- Rotting Oranges — the queue side of this topic: multi-source BFS where the queue's contents and order genuinely matter.
FAQ
What is a primitive parentheses string?
A primitive is a nonempty valid parentheses string that cannot be split into two nonempty valid parts. Equivalently, it's a balanced string whose running depth touches zero only at the very end. "(()())" is primitive; "()()" is not, because it splits into "()" and "()". Every valid parentheses string decomposes into a unique sequence of primitives, and this problem strips the single outermost pair from each one.
Why doesn't Remove Outermost Parentheses need an actual stack?
Because with one bracket type and guaranteed-valid input, a stack of open parentheses carries no information beyond its height — every entry is the same '(' character. The algorithm only ever needs to know whether the current nesting depth is zero (shell) or positive (inner content), and a single integer counter answers that in O(1) space. Stacks become necessary again when different opener types must be matched to specific closers, as in Valid Parentheses.
What is the time and space complexity of the depth counter solution?
O(n) time and O(1) extra space. The loop reads each character exactly once and does constant work per character: one comparison, one counter update, and possibly one append. The only working state is the depth integer; the output string itself is part of the answer, not overhead. Approaches that first split the input into primitive substrings are also O(n) time but pay O(n) additional memory for the intermediate copies.
Why does the order of updating depth matter?
The depth > 0 check must measure whether the character sits strictly inside a primitive, and the two bracket directions cross the boundary at different moments. An opening ( belongs to the shell when depth is 0 before it takes effect, so you check first and increment after. A closing ) belongs to the shell when it brings depth to 0, so you decrement first and check after. Swap either order and every primitive's shell brackets leak into the output.
Does the depth counting trick work with multiple bracket types?
No. The counter works precisely because all openers are interchangeable — the stack it replaces would contain nothing but identical '(' entries. With mixed types like ([{, a closing bracket must match the specific most-recent opener, which means you need the stack's contents, not just its size. That distinction is exactly why Valid Parentheses, which allows three bracket types, keeps its stack.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.