Remove the Outermost Parentheses From Every Primitive Group

Easy10–15 min

Topics

StringStack

Companies

AmazonFacebookBloomberg

A string is a "primitive" parentheses group if it's non-empty, balanced, and never dips back to depth 0 in the middle — s is always a sequence of these primitive groups placed back to back. Given a valid parentheses string s, remove the outermost parentheses of every primitive group and return what's left. Tracking depth as you scan and slicing out each group once its depth returns to 0 works, but building each slice separately means an extra pass through the substring boundaries. The faster approach skips slicing entirely: classify each character in a single pass by checking depth right before incrementing (for an opener) or right after decrementing (for a closer) — a depth of exactly 0 at that check means the character is an outermost paren to drop, anything else means it's an inner paren to keep.

Test Case 1:

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

Output:"()()()"

Explanation:s splits into two primitive groups — "(()())" and "(())". Stripping each group's outermost pair leaves "()()" and "()", joined as "()()()".

Test Case 2:

Input:s = "()()"

Output:""

Explanation:Two primitive groups, each just "()". Stripping the outer pair from each leaves nothing behind.

Test Case 3:

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

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

Explanation:Two primitive groups — "(()(()))" and "(())". Stripping only the outermost pair of each keeps all the inner structure intact.

Constraints

◆1 ≤ s.length ≤ 5 × 10⁴
◆s consists only of '(' and ')'
◆s is a valid parentheses string

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (parentheses) — 4-14 characters, balanced ( and ) only

1	class Solution {
2	public String removeOuterParentheses(String s) {
3	StringBuilder result = new StringBuilder();
4	int depth = 0;
5	for (char c : s.toCharArray()) {
6	if (c == '(') {
7	if (depth > 0) result.append(c);
8	depth++;
9	} else {
10	depth--;
11	if (depth > 0) result.append(c);
12	}
13	}
14	return result.toString();
15	}
16	}
17

(

)

(

)

(

)

Variables

depth0

INITIALIZE

Start depth at 0. Walk the string once, classifying each character by depth alone — no slicing needed.

Step 1 / 12

Approach & Solutions

Brute Force — Track Depth, Slice Each Group

Brute

A "primitive" group is a maximal balanced run of parentheses that never dips back to depth 0 in the middle — s is just a sequence of these groups placed back to back. Track depth as you scan: every '(' increases it, every ')' decreases it. Whenever depth returns to 0, you've just closed one whole primitive group — slice out everything between its outer pair (start+1 to i, exclusive of both ends) and append it to the result.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int start = 0;
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') depth++;
            else depth--;
            if (depth == 0) {
                result.append(s, start + 1, i);
                start = i + 1;
            }
        }
        return result.toString();
    }
}

Optimal — Single Pass Depth Classification

Optimal

No slicing needed at all — classify each character as you scan. For an opening paren, check depth BEFORE incrementing: if depth was 0, this is a group's outermost opener, skip it; otherwise it's an inner paren, keep it. For a closing paren, decrement depth FIRST, then check: if depth is now 0, this was a group's outermost closer, skip it; otherwise it's an inner paren, keep it. One pass, no extra slicing pass required.