☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Remove Outermost Parentheses

Medium TUF ID 892 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A valid parentheses string is either empty, or ( + A + ) where A is valid, or A + B where both A and B are valid. Every non-empty valid string can be cut into primitives: pieces that are themselves valid but cannot be split into two smaller non-empty valid strings. For example (()())(()) is the concatenation of the two primitives (()()) and (()).

You are given a valid parentheses string s. Remove the outermost pair of parentheses of every primitive and return what is left, concatenated in order.

Constraints: 0 ≤ |s| ≤ 10^5, s contains only ( and ), and s is guaranteed to be valid (it is balanced and no prefix has more closers than openers).

Example 1

s = "(()())(())"
answer = "()()()"       // primitives (()()) and (()) become ()() and ()

Example 2

s = "(()())(())(()(()))"
answer = "()()()()(())" // the third primitive (()(())) loses its outer pair and becomes ()(())

Example 3

s = "()()"
answer = ""             // each primitive is just an outer pair, so nothing remains

Approach 1: Brute force, split into primitives and strip each one

Intuition. The statement is a recipe: find the primitives, then drop the first and last character of each. A primitive ends exactly where the running count of open brackets returns to zero, because at that moment every bracket opened so far has been closed and nothing from before can be glued to what follows without being splittable. So one pass with a depth counter locates all the cut points, and a second pass trims each piece.

Algorithm.

  1. Keep depth (open brackets not yet closed) and start (where the current primitive began).
  2. Scan s; add 1 for ( and -1 for ).
  3. Whenever depth becomes 0, the substring s[start..i] is a primitive: store it and set start = i + 1.
  4. For each stored primitive append everything except its first and last character to the output.
static String bruteForce(String s) {
    List<String> primitives = new ArrayList<>();
    int depth = 0, start = 0;
    for (int i = 0; i < s.length(); i++) {
        depth += s.charAt(i) == '(' ? 1 : -1;
        if (depth == 0) {                              // s[start..i] is one primitive
            primitives.add(s.substring(start, i + 1));
            start = i + 1;
        }
    }
    StringBuilder out = new StringBuilder();
    for (String p : primitives) out.append(p, 1, p.length() - 1);   // drop p[0] and p[last]
    return out.toString();
}

Complexity. Time O(n): both passes touch each character a constant number of times. Space O(n): the list of primitives holds a copy of the whole input before the output is built.

This is already linear, so it is “brute force” only in the sense that it materialises the intermediate list of substrings. Each substring call copies characters, so the input is copied twice: once into the pieces and once into the result. The next two approaches build the answer directly.

Approach 2: Better, an explicit stack

Intuition. Whenever you see a bracket-matching problem, a stack is the natural tool: push on (, pop on ). The outermost ( of a primitive is the one pushed onto an empty stack, and the outermost ) is the one whose pop empties the stack. Every other bracket lies strictly inside a primitive and must be kept. So the rule is: keep a ( only if the stack is non-empty before pushing it, and keep a ) only if the stack is non-empty after popping its partner.

Algorithm.

  1. Create an empty stack and an output builder.
  2. For each character c:
    • If c == '(': if the stack is not empty, append c; then push c.
    • If c == ')': pop; if the stack is still not empty, append c.
  3. Return the output.
static String better(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    StringBuilder out = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c == '(') {
            if (!stack.isEmpty()) out.append(c);       // not an outermost opener
            stack.push(c);
        } else {
            stack.pop();
            if (!stack.isEmpty()) out.append(c);       // not an outermost closer
        }
    }
    return out.toString();
}

Complexity. Time O(n): one pass with constant work per character. Space O(n): the stack can grow to n/2 for a fully nested input like ((((...)))).

The order of the two statements in each branch is the whole algorithm. Checking emptiness before the push (for () and after the pop (for )) is what makes the outermost pair, and only that pair, disappear.

Approach 3: Optimal, replace the stack with a counter

Intuition. Look at what the stack in Approach 2 actually stores: only ( characters. We never read the popped value, we only ask whether the stack is empty. A stack whose contents are all identical is fully described by its size, so an int depth can replace it. The emptiness test “stack is non-empty” becomes depth > 0.

Algorithm.

  1. Set depth = 0.
  2. For each character c:
    • If c == '(': if depth > 0, append c; then depth++.
    • If c == ')': depth--; if depth > 0, append c.
  3. Return the output.
static String optimal(String s) {
    StringBuilder out = new StringBuilder();
    int depth = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            if (depth > 0) out.append(c);              // depth before the push
            depth++;
        } else {
            depth--;
            if (depth > 0) out.append(c);              // depth after the pop
        }
    }
    return out.toString();
}

Dry run on s = "(()())(())":

i c depth before action depth after out
0 ( 0 skip (outermost) 1  
1 ( 1 append 2 (
2 ) 2 append (depth 1 after pop) 1 ()
3 ( 1 append 2 ()(
4 ) 2 append 1 ()()
5 ) 1 skip (depth 0 after pop) 0 ()()
6 ( 0 skip (outermost) 1 ()()
7 ( 1 append 2 ()()(
8 ) 2 append 1 ()()()
9 ) 1 skip 0 ()()()

Complexity. Time O(n): one pass. Space O(1) extra, not counting the output string that every solution must produce.

An equivalent way to phrase the rule that some people find easier to remember: a ( is kept if the depth after pushing is at least 2, and a ) is kept if the depth before popping is at least 2. In both phrasings the brackets at depth 1 are exactly the outermost ones.

Edge cases and pitfalls