Remove Outermost Parentheses: Depth Counter Pattern

You are given a valid parentheses string s. A "primitive" parentheses string is one that is non-empty and cannot be split into two non-empty valid strings. The task is to remove the outermost parentheses of every primitive group and return the resulting string.

This is LeetCode 1021: Remove Outermost Parentheses, an easy problem that introduces the depth counter pattern. The core idea is elegant: track how deep you are in the nesting, and only keep characters that are not at the outermost level.

Why this problem matters

Remove Outermost Parentheses is a great first encounter with the depth tracking technique. Many harder problems (nested expressions, calculator parsing, decode strings) require you to know which nesting level you are at. This problem isolates that skill in a clean, minimal setting.

It also reinforces the idea that you do not need a literal stack data structure for every parentheses problem. A simple integer counter is enough when all you care about is depth, not what specific characters are on the stack.

The key insight

Every valid parentheses string can be decomposed into primitive groups. Within each group, the first ( and last ) are the outermost pair. You can identify these outermost characters by tracking depth:

• When you see ( and depth is currently 0, that is an outer opening parenthesis. Increment depth, but do not add the character to the result.
• When you see ( and depth is already 1 or more, that is an inner character. Increment depth and add it.
• When you see ), decrement depth first. If depth is still above 0, it is an inner character, so add it. If depth is now 0, it is the outer closing parenthesis, so skip it.

The depth counter tells you everything. Outer characters are the ones where depth transitions from 0 to 1 (opening) or from 1 to 0 (closing). Every other character is inner and belongs in the result.

The solution

def removeOuterParentheses(s):
    result = []
    depth = 0
    for ch in s:
        if ch == '(':
            if depth > 0:
                result.append(ch)
            depth += 1
        else:
            depth -= 1
            if depth > 0:
                result.append(ch)
    return ''.join(result)

The logic breaks into two cases. For an opening parenthesis, you check depth before incrementing. If depth is already above 0, the character is inner. For a closing parenthesis, you decrement depth first, then check. If depth is still above 0 after decrementing, the character is inner.

This ordering matters. The outer ( always arrives when depth is 0 (about to become 1). The outer ) always brings depth from 1 back to 0. By checking at the right moment, you cleanly filter out exactly the outermost characters.

Visual walkthrough

Let's trace through "(()())(())" character by character, watching the depth counter and result string grow.

After processing all 10 characters, the result is "()()()". The four outermost parentheses (indices 0, 5, 6, 9) were skipped, and the six inner characters were kept.

Complexity analysis

Time: O(n). You iterate through each character exactly once. The depth check, increment, and append operations are all O(1). Total work scales linearly with the length of the input string.

Space: O(n). The result list can hold up to n - 2 characters in the worst case (when the entire string is one primitive group like "((...))" with all inner characters kept). The depth counter itself is O(1), but the output dominates.

The building blocks

1. Depth tracking with an integer counter

Instead of pushing and popping from a stack, you maintain a single integer that goes up on ( and down on ). This is the right tool when you only need to know the current nesting level, not what specific characters are at each level.

depth = 0
for ch in s:
    if ch == '(':
        depth += 1
    else:
        depth -= 1

This counter is O(1) space and gives you instant access to the current depth. You will use this same building block in problems like Score of Parentheses and Maximum Nesting Depth of the Parentheses.

2. Conditional character collection

The pattern of iterating through a string and selectively appending characters to a result list is fundamental. The condition changes per problem, but the structure is always the same: loop, check, maybe append, join at the end.

result = []
for ch in s:
    if should_keep(ch):
        result.append(ch)
return ''.join(result)

Building the result as a list and joining once at the end is more efficient than concatenating strings in a loop, since Python string concatenation creates a new string each time.

Edge cases

• Single primitive group: "(())" becomes "()". The entire string is one group, so only the first and last characters are removed.
• Already flat: "()()()" becomes "". Each group is "()" with nothing inside, so removing the outer parentheses leaves nothing.
• Deeply nested: "(((())))" becomes "((()))". Only the very outermost pair is removed, since the whole string is a single primitive.
• Many small groups: "()()()()" becomes "". Four primitive groups, each empty inside.
• Mixed nesting depths: "(()())(())" becomes "()()()". Each primitive group contributes its inner characters independently.

From understanding to recall

The depth counter pattern for this problem feels obvious once you see it. Check depth, increment or decrement at the right moment, skip outer characters. Simple. But when you sit down to code it from scratch a few weeks later, the details get fuzzy. Was it "check before increment" or "increment before check"? Which direction applies to which bracket?

That is the gap between understanding and recall. You understood the solution perfectly, but reproducing it under time pressure is a different skill entirely. Spaced repetition bridges that gap. You practice writing the solution from memory at increasing intervals, and each repetition strengthens the neural pathways for the specific ordering of operations. After a few cycles, the depth counter pattern is automatic.

Related posts

• Valid Parentheses - The classic stack-based bracket matching problem
• Score of Parentheses - Depth tracking with a twist, computing scores based on nesting
• Minimum Add to Make Parentheses Valid - Counting unmatched brackets using a similar counter approach

CodeBricks uses spaced repetition to turn pattern recognition into automatic recall. Instead of re-reading solutions, you reconstruct them from memory at scientifically optimized intervals. The depth counter pattern, the check-then-increment ordering, the conditional append loop, they all become second nature.