Remove Outermost Parentheses in a Valid Parentheses String Optimal Solution

Problem Statement❯

Given a valid parentheses string s, your task is to remove the outermost parentheses from each primitive valid parentheses substring.

A primitive string is a non-empty valid parentheses string that cannot be broken into smaller non-empty valid strings.
Your result should contain the inner content of each primitive group, without their outermost brackets.

Return the final processed string after removing the outermost parentheses from every primitive.

Examples❯

Input	Output	Description
"(()())(())"	"()()()"	Two primitive parts: "(()())" → "()()", "(())" → "()"
"(()())(())(()(()))"	"()()()()(())"	Removes outer parentheses from each primitive group
"()()"	""	Each "()" is primitive, and its outer parentheses are removed
"((()))"	"(())"	Single primitive, outermost removed
""	""	Empty input returns empty output

Visualization Player

Solution❯

To solve this problem, we need to understand what it means to remove the outermost parentheses from a primitive group in a valid parentheses string.

A primitive parentheses string is one that is valid (i.e., balanced) and cannot be divided further into smaller valid parts. For example, "(())" and "()" are primitives, but "(()())(())" is not a primitive — it's made of multiple primitives.

Our goal is to go through the input and for every such primitive group, remove its first '(' and last ')'. For example, in "(()())", the primitive is the whole string, and removing its outermost parentheses gives "()()".

How We Approach This

We walk through the string character by character. As we go, we use a counter open to track how deep we are in the parentheses nesting:

When we see '(', we increase the nesting count.
When we see ')', we decrease the nesting count.

But here's the trick: we don't include the first '(' when open goes from 0 to 1 (this is the outermost), and we don't include the ')' that causes open to go back to 0 (this is the closing of the outermost).

Example Cases

Let’s take "(()())(())" as an example:

The first primitive is "(()())" → we remove the outermost '(', ')' → becomes "()()"
The second primitive is "(())" → becomes "()"
Final result: "()()()"

Edge Cases

If the input is an empty string "", there’s nothing to process, so we return "".
If the string consists only of "()()", each pair is its own primitive, and both outer parentheses are removed, leaving an empty string.
If the input is deeply nested like "((()))", then removing the outermost parentheses gives "(())".

This method works efficiently in one pass through the string and uses only a simple counter — making it an optimal solution.

Algorithm Steps❯

Given a valid parentheses string s.
Initialize an empty result string and a counter open = 0.
Iterate through each character in the string:
→ If the character is '(', increment open.
→ If open > 1 after incrementing, add '(' to the result.
→ If the character is ')', decrement open.
→ If open > 0 before decrementing, add ')' to the result.
By skipping the first '(' and the last ')' of each primitive, we effectively remove the outermost parentheses.
Return the final result string.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def remove_outer_parentheses(s):
    result = []
    open_count = 0
    
    for char in s:
        if char == '(':  # Increase count for open
            if open_count > 0:
                result.append(char)  # Don't include outermost
            open_count += 1
        else:
            open_count -= 1
            if open_count > 0:
                result.append(char)  # Don't include outermost

    return ''.join(result)

# Sample Input
s = "(()())(())"
print("Result:", remove_outer_parentheses(s))

⬅ Previous TopicFind Longest Palindromic Substring Without Dynamic Programming

Next Topic ⮕Find Maximum Nesting Depth of Parentheses - Optimal Stack-Free Solution