Problem

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 = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

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

Examples

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 "" + "" = "".

Solution

Method 1 - Using counter

The problem can be solved by iterating through the string and using a counter to track the depth of parentheses. We:

  1. Initialize a counter to zero.
  2. Traverse the string character by character:
    • Increase the counter when encountering '('.
    • Decrease the counter when encountering ')'.
    • Add the character to the result if the counter is greater than one (for open parenthesis) or greater than zero (for close parenthesis).
  3. This way, the outermost parentheses are not included in the result.

This approach ensures that we correctly identify and exclude the outermost parentheses for each primitive valid parentheses substring.

Code

Java
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        int depth = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (depth > 0) {
                    ans.append(c);
                }
                depth++;
            } else if (c == ')') {
                depth--;
                if (depth > 0) {
                    ans.append(c);
                }
            }
        }
        
        return ans.toString();
    }
}
Python
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        depth = 0

        for c in s:
            if c == '(':
                if depth > 0:
                    ans.append(c)
                depth += 1
            elif c == ')':
                depth -= 1
                if depth > 0:
                    ans.append(c)

        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since we traverse the string once.
  • 🧺 Space complexity: O(n) for the result string.