Remove Outermost Parentheses

Easy

#0975Time: O(N), where N is the length of the string. We iterate through the string once. The `substring` operation in Java takes time proportional to the length of the substring. Since the sum of lengths of all substrings is N, the total time complexity remains O(N).Space: O(N), where N is the length of the input string. This is required for the `StringBuilder` that stores the result, which can have a length up to N-2.

Data structures

String Stack

Prompt

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

For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P₁ + P₂ + ... + P_k, where P_i are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

Input: s = "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation: 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

Input: s = "()()"
Output: ""
Explanation: 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

Constraints:

1 <= s.length <= 10⁵
s[i] is either '(' or ')'.
s is a valid parentheses string.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly follows the problem's definition. It first identifies the primitive components of the input string by tracking the balance of parentheses. Once a primitive component is identified, its outermost parentheses are removed, and the inner content is appended to the result.

Algorithm

Initialize a StringBuilder result to store the final string.
Initialize an integer balance = 0 to track the nesting level of parentheses.
Initialize an integer start = 0 to mark the beginning of the current primitive component.
Iterate through the input string s from i = 0 to s.length() - 1.
If s.charAt(i) == '(', increment balance.
If s.charAt(i) == ')', decrement balance.
If balance == 0, we have found a complete primitive component from index start to i.
Append the inner part of this component (s.substring(start + 1, i)) to the result.
Update start to i + 1 to mark the beginning of the next component.
After the loop, return result.toString().

Walkthrough

We iterate through the string while maintaining a balance counter. The counter is incremented for an opening parenthesis ( and decremented for a closing one ). A primitive string is a valid parentheses string that cannot be split into two non-empty valid parentheses strings. This means that for a primitive string, the balance counter only returns to zero at the very end. Therefore, whenever our balance counter, which starts at zero, returns to zero during the iteration, we have identified the end of a primitive component. We then extract this component, remove its first and last characters (the outermost parentheses), and append the remaining part to our result. We then reset the starting point for the next primitive component and continue until the entire string is processed.

1class Solution {2    public String removeOuterParentheses(String s) {3        StringBuilder result = new StringBuilder();4        int balance = 0;5        int start = 0;6        for (int i = 0; i < s.length(); i++) {7            char c = s.charAt(i);8            if (c == '(') {9                balance++;10            } else {11                balance--;12            }13            if (balance == 0) {14                // Found a primitive component from start to i15                // Append the content inside the outermost parentheses16                result.append(s.substring(start + 1, i));17                // Update start for the next primitive component18                start = i + 1;19            }20        }21        return result.toString();22    }23}

Complexity

Time

O(N), where N is the length of the string. We iterate through the string once. The `substring` operation in Java takes time proportional to the length of the substring. Since the sum of lengths of all substrings is N, the total time complexity remains O(N).

Space

O(N), where N is the length of the input string. This is required for the `StringBuilder` that stores the result, which can have a length up to N-2.

Trade-offs

Pros

The logic is a direct translation of the problem statement, making it relatively easy to understand and implement.

Cons

Involves creating intermediate substrings, which can be less memory-efficient and slightly slower due to object creation overhead compared to a single-pass approach.

This is a more optimized approach that builds the result string in a single pass without explicitly decomposing the string into primitive parts. It uses a counter to determine whether a parenthesis is an outermost one and should be skipped.

Algorithm

Initialize an empty StringBuilder result.
Initialize an integer balance = 0.
Iterate through each character c of the input string s.
If c is (:
- If balance > 0, append c to result.
- Increment balance.
If c is ):
- Decrement balance.
- If balance > 0, append c to result.
Return result.toString().

Walkthrough

The core idea is to identify which parentheses should be included in the final result. We iterate through the string, maintaining a balance counter.

An opening parenthesis ( should be included if and only if it's not the first one in a primitive component. The first ( of a primitive component is encountered when the balance is 0. Any subsequent ( within that component will be encountered when the balance is greater than 0. So, we append an opening parenthesis if balance > 0 before we increment the counter.
A closing parenthesis ) should be included if and only if it's not the last one in a primitive component. The last ) of a primitive component is the one that makes the balance return to 0. Any other ) will be encountered when the balance is greater than 1. So, we append a closing parenthesis if balance > 0 after we decrement the counter.

This allows us to build the final string in one go.

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

Complexity

Time

O(N), where N is the length of the string. We perform a single pass through the string, with constant time operations at each character.

Space

O(N) to store the `StringBuilder` for the result. In the worst case, the result string's length is close to N.

Trade-offs

Pros

Highly efficient as it processes the string in a single pass.
Avoids creating intermediate substrings, reducing memory allocations and overhead.

Cons

The logic is slightly more abstract than the decomposition approach, as it doesn't explicitly handle primitive components.

Solutions

Solution

1class Solution {2public3  String removeOuterParentheses(String s) {4    StringBuilder ans = new StringBuilder();5    int cnt = 0;6    for (int i = 0; i < s.length(); ++i) {7      char c = s.charAt(i);8      if (c == '(') {9        if (++cnt > 1) {10          ans.append(c);11        }12      } else {13        if (--cnt > 0) {14          ans.append(c);15        }16      }17    }18    return ans.toString();19  }20}

1class Solution {2public:3  string removeOuterParentheses(string s) {4    string ans;5    int cnt = 0;6    for (char &c : s) {7      if (c == '(') {8        if (++cnt > 1) {9          ans.push_back(c);10        }11      } else {12        if (--cnt) {13          ans.push_back(c);14        }15      }16    }17    return ans;18  }19};

1class Solution:2    def removeOuterParentheses(self, s: str) -> str: ans = [] cnt = 0 for c in s: if c == '(': cnt += 1 if cnt > 1: ans . append(c) else: cnt -= 1 if cnt > 0: ans . append(c) return '' . join(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem