Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

Remove Outermost Parentheses

Easy · Strings · Asked at Amazon, Google, TCS, Infosys

The string is a valid parentheses string. Split it into its primitive parts (non-empty valid strings that cannot be split further) and remove the outermost pair of each part. Print the result.

Input

A single string s of ( and ).

Output

The string after removing the outermost parentheses. It is guaranteed not to be empty.

Constraints

Track the depth: print a "(" only if the depth was already > 0 before it, and a ")" only if the depth stays > 0 after it.

Example 1

Input

(()())(())

Output

()()()

Example 2

Input

(()())(())(()(()))

Output

()()()()(())

Hints

  1. Keep a depth counter. A primitive part ends whenever the depth returns to 0.
  2. The outermost "(" is the one seen at depth 0; the outermost ")" is the one that brings depth back to 0. Skip exactly those.

Approach

Scan once with depth. For "(": append it only if depth > 0, then increment. For ")": decrement first, then append only if depth > 0. This drops exactly the first and last bracket of every primitive part without splitting the string explicitly.

Complexity: O(n) time · O(n) space for the output

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, out;
    cin >> s;
    int depth = 0;
    for (char c : s) {
        if (c == '(') {
            if (depth > 0) out += c;
            depth++;
        } else {
            depth--;
            if (depth > 0) out += c;
        }
    }
    cout << out << "\n";
    return 0;
}

Python solution

s = input().strip()
out, depth = [], 0
for c in s:
    if c == "(":
        if depth > 0:
            out.append(c)
        depth += 1
    else:
        depth -= 1
        if depth > 0:
            out.append(c)
print("".join(out))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String s = new Scanner(System.in).next();
        StringBuilder out = new StringBuilder();
        int depth = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (depth > 0) out.append(c);
                depth++;
            } else {
                depth--;
                if (depth > 0) out.append(c);
            }
        }
        System.out.println(out);
    }
}

Solve Remove Outermost Parentheses online · All practice problems