Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Remove Outermost Parentheses

EASYProblemSolveExternal Links

Description

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

A valid parentheses string is called primitive if it is non-empty and cannot be split into two non-empty valid parentheses strings. For example, "(())" is primitive because you cannot break it into two non-empty valid parts, but "(()())" is also primitive. On the other hand, "()(())" is not primitive because it can be split into "()" + "(())".

Every valid parentheses string has a unique primitive decomposition — it can be written as a concatenation of primitive strings: s = P₁ + P₂ + ... + Pₖ.

Given a valid parentheses string s, remove the outermost parentheses from each primitive substring in its primitive decomposition, and return the resulting string.

Examples

Example 1

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

Output: "()()()"

Explanation: The primitive decomposition is "(()())" + "(())". Removing the outermost parentheses from "(()())" gives "()()", and removing them from "(())" gives "()". Concatenating the results: "()()" + "()" = "()()()".

Example 2

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

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

Explanation: The primitive decomposition is "(()())" + "(())" + "(()(()))". Removing outermost parentheses from each: "()()" + "()" + "()(())" = "()()()()(())".

Example 3

Input: s = "()()"

Output: ""

Explanation: The primitive decomposition is "()" + "()". Each primitive is just a pair of parentheses with nothing inside. Removing the outermost parentheses from each yields empty strings. The result is "" + "" = "".

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward approach is to first split the string into its primitive components, and then strip the first and last character from each component.

How do we find the primitive decomposition? A primitive string starts when we encounter an opening parenthesis that begins a new "balanced group" and ends when the running balance of parentheses returns to zero. We can scan left to right, maintaining a counter: increment for '(' and decrement for ')'. Whenever the counter hits zero, we've found the end of one primitive substring.

Think of it like balancing a checkbook. Every '(' is a deposit of 1andevery′)′isawithdrawalof1 and every ')' is a withdrawal of 1. When your balance returns to $0, you've completed one full cycle — that cycle is one primitive string. You then peel off the first and last transaction (the outermost parentheses) and keep only what's inside.

Step-by-Step Explanation

Let's trace through with s = "(()())(())":

Step 1: Initialize balance = 0, start = 0, primitives = [].

Step 2: Process s[0] = '('. balance = 1. Not zero yet, continue.

Step 3: Process s[1] = '('. balance = 2. Continue.

Step 4: Process s[2] = ')'. balance = 1. Continue.

Step 5: Process s[3] = '('. balance = 2. Continue.

Step 6: Process s[4] = ')'. balance = 1. Continue.

Step 7: Process s[5] = ')'. balance = 0. Found primitive from index 0 to 5: "(()())". Store it.

  • Set start = 6.

Step 8: Process s[6] = '('. balance = 1. Continue.

Step 9: Process s[7] = '('. balance = 2. Continue.

Step 10: Process s[8] = ')'. balance = 1. Continue.

Step 11: Process s[9] = ')'. balance = 0. Found primitive from index 6 to 9: "(())". Store it.

Step 12: For each primitive, strip the first and last character:

  • "(()())" → "()()"
  • "(())" → "()"

Step 13: Concatenate results: "()()" + "()" = "()()()".

Brute Force — Find Primitives Then Strip Outer Parentheses — Watch how we scan the string tracking the balance counter. Each time the balance returns to zero, we've identified a primitive substring. Then we remove the first and last character of each.

Algorithm

  1. Initialize balance = 0, start = 0, and an empty list primitives
  2. For each index i in the string:
    • If s[i] == '(', increment balance
    • If s[i] == ')', decrement balance
    • If balance reaches 0:
      • Extract substring s[start..i] as a primitive
      • Add the substring without its first and last character to the result
      • Set start = i + 1
  3. Concatenate all stripped primitives and return

Code

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result = "";
        int balance = 0;
        int start = 0;
        
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                balance++;
            } else {
                balance--;
            }
            
            if (balance == 0) {
                // Found a primitive from start to i
                // Strip outermost: take s[start+1 .. i-1]
                result += s.substr(start + 1, i - start - 1);
                start = i + 1;
            }
        }
        
        return result;
    }
};
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = []
        balance = 0
        start = 0
        
        for i, char in enumerate(s):
            if char == '(':
                balance += 1
            else:
                balance -= 1
            
            if balance == 0:
                # Found primitive from start to i
                # Strip outermost: take s[start+1 : i]
                result.append(s[start + 1 : i])
                start = i + 1
        
        return ''.join(result)
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int balance = 0;
        int start = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                balance++;
            } else {
                balance--;
            }
            
            if (balance == 0) {
                result.append(s, start + 1, i);
                start = i + 1;
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan the string once to find primitives (O(n)), and extracting substrings takes O(n) total across all primitives. Overall: O(n).

Space Complexity: O(n)

We store the primitives list and the result string. In the worst case, these together use O(n) space. The algorithm itself uses only O(1) auxiliary variables (balance, start), but the output string requires O(n) space.

Why This Approach Is Not Efficient

The brute force approach is actually O(n) in time, which is already optimal for this problem since we must read every character at least once. However, the two-pass nature (first identify primitives, then strip) and the substring extraction create intermediate strings that add overhead.

We can do better in terms of simplicity and constant factors by eliminating the need to track primitive boundaries at all. Instead of finding each primitive and then stripping it, we can decide character-by-character whether to include it in the result — in a single pass, without any substring operations.

The key observation: a character is an "outermost" parenthesis if and only if it is the '(' that starts a primitive (when balance goes from 0 to 1) or the ')' that ends a primitive (when balance goes from 1 to 0). All other characters are inner characters that should be kept.

Optimal Approach - Single-Pass Counter

Intuition

We can solve this in a single elegant pass without ever explicitly identifying primitive boundaries or extracting substrings.

The insight is simple: keep a running depth counter. For each character:

  • If it's '(': increment depth. If depth is now greater than 1, this '(' is an inner character — include it.
  • If it's ')': if depth is greater than 1, this ')' is an inner character — include it. Then decrement depth.

Why does this work? The outermost parentheses of every primitive are exactly the characters where depth transitions between 0 and 1. The opening '(' of a primitive is the one that takes depth from 0 to 1 — we skip it. The closing ')' of a primitive is the one that takes depth from 1 to 0 — we skip it too. Every other character lives at depth ≥ 2 and is an inner character that we keep.

Imagine you're walking through a building with nested rooms. Depth 0 is outside. Depth 1 means you're just inside the outermost door. Depth 2+ means you're in an inner room. You want to record everything that happens in inner rooms but ignore the outermost doors themselves.

Step-by-Step Explanation

Let's trace with s = "(()())(())":

Step 1: depth = 0, result = "". Start scanning.

Step 2: s[0] = '('. depth becomes 1. depth == 1 means this is an outermost '(' → SKIP.

  • result = ""

Step 3: s[1] = '('. depth becomes 2. depth > 1 → this is INNER → INCLUDE.

  • result = "("

Step 4: s[2] = ')'. depth is 2 > 1 → INCLUDE first, then decrement. depth becomes 1.

  • result = "()"

Step 5: s[3] = '('. depth becomes 2. depth > 1 → INCLUDE.

  • result = "()("

Step 6: s[4] = ')'. depth is 2 > 1 → INCLUDE, then depth becomes 1.

  • result = "()()"

Step 7: s[5] = ')'. depth is 1, not > 1 → this is an outermost ')' → SKIP. depth becomes 0.

  • result = "()()"

Step 8: s[6] = '('. depth becomes 1. Outermost '(' → SKIP.

  • result = "()()"

Step 9: s[7] = '('. depth becomes 2. Inner → INCLUDE.

  • result = "()()("

Step 10: s[8] = ')'. depth is 2 > 1 → INCLUDE, depth becomes 1.

  • result = "()()()"

Step 11: s[9] = ')'. depth is 1 → outermost ')' → SKIP. depth becomes 0.

  • result = "()()()"

Single-Pass Counter — Include Only Inner Characters — Watch how the depth counter elegantly distinguishes outermost parentheses (depth transitions 0↔1) from inner characters (depth ≥ 2). Only inner characters make it into the result.

Algorithm

  1. Initialize depth = 0 and an empty result string
  2. For each character c in s:
    • If c == '(':
      • Increment depth
      • If depth > 1, append '(' to result (it's an inner character)
    • If c == ')':
      • If depth > 1, append ')' to result (it's an inner character)
      • Decrement depth
  3. Return result

Code

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result;
        int depth = 0;
        
        for (char c : s) {
            if (c == '(') {
                depth++;
                if (depth > 1) {
                    result += c;
                }
            } else {
                if (depth > 1) {
                    result += c;
                }
                depth--;
            }
        }
        
        return result;
    }
};
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = []
        depth = 0
        
        for c in s:
            if c == '(':
                depth += 1
                if depth > 1:
                    result.append(c)
            else:
                if depth > 1:
                    result.append(c)
                depth -= 1
        
        return ''.join(result)
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int depth = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                depth++;
                if (depth > 1) {
                    result.append(c);
                }
            } else {
                if (depth > 1) {
                    result.append(c);
                }
                depth--;
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan the string exactly once, performing O(1) work per character (a comparison, an increment/decrement, and possibly an append). Total: O(n) where n is the length of the string.

Space Complexity: O(n)

The result string can be at most n-2 characters long (if the entire string is one primitive, we remove just 2 characters). We use O(1) auxiliary space beyond the output — just the depth integer. If we don't count the output string, the auxiliary space is O(1).

This is optimal: we cannot do better than O(n) time since we must read every character, and we cannot avoid O(n) output space.