Remove Outermost Parentheses

Easy
238.

Remove Outermost Parentheses

Remove Outermost Parentheses is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.

A valid parentheses string is primitive if it is non-empty and cannot be split into two non-empty valid parentheses strings.

Every valid parentheses string s decomposes uniquely into primitive pieces. Remove the outermost parentheses of each piece and return the concatenation of what is left.

Example 1

Input
s = "(()())(())"
Output
()()()
Explanation
The pieces are "(()())" and "(())"; stripping the outer layer leaves "()()" and "()".

Example 2

Input
s = "(()())(())(()(()))"
Output
()()()()(())

Example 3

Input
s = "()()"
Output
Explanation
Both pieces are bare, so nothing survives.

Constraints

  • 1 <= s.length <= 40
  • s is a valid parentheses string.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Outermost Parentheses — Problem & Solution

Remove Outermost Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Remove Outermost Parentheses is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Stack
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A valid parentheses string is primitive if it is non-empty and cannot be split into two non-empty valid parentheses strings.

Every valid parentheses string s decomposes uniquely into primitive pieces. Remove the outermost parentheses of each piece and return the concatenation of what is left.

Example 1

Input: s = "(()())(())"
Output: ()()()
Explanation: The pieces are "(()())" and "(())"; stripping the outer layer leaves "()()" and "()".

Example 2

Input: s = "(()())(())(()(()))"
Output: ()()()()(())

Example 3

Input: s = "()()"
Output: 
Explanation: Both pieces are bare, so nothing survives.

Constraints

  • 1 <= s.length <= 40
  • s is a valid parentheses string.

Hints for Remove Outermost Parentheses

  1. Hint 1

    Track the nesting depth as you scan.

  2. Hint 2

    An opening bracket at depth 0 and a closing bracket that returns to depth 0 are exactly the outer layer of a primitive piece — skip those.

  3. Hint 3

    Careful with the order: increment the depth after deciding about a (, and decrement before deciding about a ).

How to solve Remove Outermost Parentheses

Track the depth. An opening bracket seen at depth 0 and a closing bracket that brings the depth back to 0 form the outer layer of a primitive — skip exactly those.

Approach

  1. Set depth = 0.
  2. For (: append it only if depth > 0, then increment.
  3. For ): decrement, then append it only if depth > 0.

Why it works

A primitive starts where the depth rises from 0 and ends where it returns to 0; the brackets at those two moments are its outermost pair. Every other bracket is interior to some primitive and is kept.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • The order of test versus update differs for ( and ) — increment after deciding, decrement before deciding.

Reference solution

Python

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

Java

public static String removeOuterParentheses(String s) {
    StringBuilder out = new StringBuilder();
    int depth = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            if (depth > 0) out.append('(');
            depth++;
        } else {
            depth--;
            if (depth > 0) out.append(')');
        }
    }
    return out.toString();
}

C++

string removeOuterParentheses(string s) {
    string out = "";
    int depth = 0;
    for (char c : s) {
        if (c == '(') {
            if (depth > 0) out += '(';
            depth++;
        } else {
            depth--;
            if (depth > 0) out += ')';
        }
    }
    return out;
}

JavaScript

var removeOuterParentheses = function(s) {
    let out = "";
    let depth = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            if (depth > 0) out += "(";
            depth++;
        } else {
            depth--;
            if (depth > 0) out += ")";
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure