{x}
blog image

Remove Outermost Parentheses

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.

 

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 <= 105
  • s[i] is either '(' or ')'.
  • s is a valid parentheses string.

Solution Explanation and Code

This problem asks to remove the outermost parentheses of every primitive valid parentheses string in the given string s. A primitive valid parentheses string is a nonempty string that cannot be further decomposed into valid parentheses substrings.

The efficient solution utilizes a counter to track the nesting level of parentheses. We iterate through the input string. If we encounter an opening parenthesis '(', we increment the counter. If the counter is greater than 1 (meaning we're inside a nested structure), we append the parenthesis to the result. Similarly, if we encounter a closing parenthesis ')', we decrement the counter. If the counter is still greater than 0 (meaning we haven't reached the outermost closing parenthesis of the current primitive string), we append the closing parenthesis to the result.

This approach avoids the need for explicitly identifying primitive substrings. The counter elegantly handles the nesting levels, ensuring only the inner parentheses are retained.

Time and Space Complexity Analysis

Time Complexity: O(N), where N is the length of the input string s. We iterate through the string once.

Space Complexity: O(N) in the worst case. The space used is proportional to the length of the resulting string, which could be as long as the input string (if there are no outermost parentheses to remove). In the best case (all outer parentheses), it will be O(1).

Code in Different Languages

The code below demonstrates this solution in several programming languages. Note that the core logic remains consistent across all implementations.

Python

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = []
        count = 0
        for char in s:
            if char == '(':
                count += 1
                if count > 1:
                    result.append(char)
            elif char == ')':
                count -= 1
                if count > 0:
                    result.append(char)
        return "".join(result)

Java

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
                if (count > 1) {
                    result.append(c);
                }
            } else if (c == ')') {
                count--;
                if (count > 0) {
                    result.append(c);
                }
            }
        }
        return result.toString();
    }
}

C++

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result = "";
        int count = 0;
        for (char c : s) {
            if (c == '(') {
                count++;
                if (count > 1) {
                    result += c;
                }
            } else if (c == ')') {
                count--;
                if (count > 0) {
                    result += c;
                }
            }
        }
        return result;
    }
};

Javascript

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    let result = "";
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (char === '(') {
            count++;
            if (count > 1) {
                result += char;
            }
        } else if (char === ')') {
            count--;
            if (count > 0) {
                result += char;
            }
        }
    }
    return result;
};

These code snippets all follow the same algorithmic approach, demonstrating its adaptability across different languages. The minor syntactic variations are typical of language differences, but the core logic for solving the problem remains unchanged.