Remove Outermost Parentheses in a Valid Parentheses String Optimal Solution

Strings

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

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

Solution❯

Understanding the Problem

We are given a valid parentheses string made up of multiple primitive parts. A primitive parentheses string is a valid sequence that cannot be split into smaller valid parts. For example, "()" and "(())" are primitives, but "(()())(())" contains multiple primitive parts.

Our task is to remove the outermost parentheses from each primitive group. That means for each such primitive, we will drop the very first '(' and the last ')'.

Step-by-Step Solution with Example

Step 1: Choose an example input

Let’s walk through the string "(()())(())".

This contains two primitive parts:

  • "(()())"
  • "(())"

Step 2: Understand how nesting works

We will use a variable open to track the depth of nesting:

  • When we see '(', we increase the open counter.
  • When we see ')', we decrease the open counter.

Step 3: Remove outermost parentheses

The outermost '(' is when open goes from 0 to 1 — we skip adding that character.

The outermost ')' is when open becomes 0 again — we also skip adding that character.

All other characters are added to the result.

Step 4: Simulate the process

For input "(()())(())":

  • First primitive: "(()())" → Remove outermost → "()()"
  • Second primitive: "(())" → Remove outermost → "()"

Final output: "()()()"

Edge Cases

  • Empty string: "" → No primitives, return ""
  • Multiple shallow primitives: "()()" → Each is primitive, removing outer gives "" for each → Final output: ""
  • Deeply nested primitive: "((()))" → One primitive → Removing outer gives "(())"

Finally

This approach efficiently processes the string in a single pass using a counter to track the nesting level. By only skipping the first and last parentheses of each primitive, we achieve the desired result. The logic is clean, fast, and works well for all types of valid input strings, including edge cases.

Algorithm Steps❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

void removeOuterParentheses(const char* s) {
    int openCount = 0;
    for (int i = 0; s[i] != '\0'; ++i) {
        if (s[i] == '(') {
            if (openCount > 0) putchar('(');
            openCount++;
        } else {
            openCount--;
            if (openCount > 0) putchar(')');
        }
    }
    printf("\n");
}

int main() {
    const char* s = "(()())(())";
    printf("Result: ");
    removeOuterParentheses(s);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...