Remove Outermost Parentheses - Practice Coding Problems

Remove Outermost Parentheses - Problem

String Stack Easy

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P₁ + P₂ + ... + Pₖ, where Pᵢ are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Input & Output

Example 1 — Two Primitives

$ Input: s = "(()())(())"

› Output: "()()(())"

💡 Note: Input has two primitives: "(()())" and "(())". Removing outer parentheses gives "()()" + "()" = "()()(())".

Example 2 — Single Primitive

$ Input: s = "(()())"

› Output: "()()"

💡 Note: Input is one primitive substring. Remove the outermost '(' and ')' to get "()()".

Example 3 — Simple Cases

$ Input: s = "()()"

› Output: ""

💡 Note: Two primitives "()" and "()". Each becomes empty after removing outer parentheses, so result is empty string.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '(' or ')'
s is a valid parentheses string

Visualization

Tap to expand

Understanding the Visualization

Input

Valid parentheses string with primitive components

Identify Primitives

Find complete primitive substrings using balance counting

Remove Outer

Skip first and last parentheses of each primitive

Key Takeaway

🎯 Key Insight: Track nesting depth to distinguish between inner and outer parentheses

Asked in

A Amazon 15 F Facebook 12 G Google 8

The key insight is to track parentheses depth and skip outermost ones. Best approach uses depth counter in single pass. Time: O(n), Space: O(n) for result string.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Find Primitives First	O(n)	O(n)	Identify all primitive substrings, then remove their outer parentheses
Stack Simulation - One Pass	O(n)	O(n)	Simulate stack to track depth and skip outermost parentheses

Brute Force - Find Primitives First — Algorithm Steps

Find all primitive substring boundaries
For each primitive, skip first and last parentheses
Concatenate the inner parts

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Primitives

Track balance to identify complete primitive substrings

Extract Inner

Remove first and last parentheses from each primitive

Concatenate

Join all inner parts together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s) {
    int len = strlen(s);
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int resultIdx = 0;
    
    // Find primitive boundaries and remove outer parentheses
    int balance = 0;
    int start = 0;
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            balance++;
        } else {
            balance--;
        }
        
        if (balance == 0) {
            // Copy inner part (skip first and last)
            for (int j = start + 1; j < i; j++) {
                result[resultIdx++] = s[j];
            }
            start = i + 1;
        }
    }
    
    result[resultIdx] = '\0';
    return result;
}

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the string of length n

✓ Linear Growth

Space Complexity

O(n)

Storage for primitive boundaries and result string

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Find Primitives First — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler