Remove Outermost Parentheses

This problem can be approached by using a stack-based solution. A counter is used to keep track of the balance of the parentheses. When we see an opening bracket, we increase the counter, and when we see a closing bracket, we decrease the counter. If we find a closing bracket and the counter is 1, we know that we’ve found a primitive string. If we find an opening bracket and the counter is not 0, we know we are not at the outermost level, so we add the parentheses to our result.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        counter = 0
        result = ""
        for char in s:
            if char == '(':
                if counter > 0:  # Not an outermost '('
                    result += char
                counter += 1
            elif char == ')':
                counter -= 1
                if counter > 0:  # Not an outermost ')'
                    result += char
        return result

This code iterates over each character in the string s. If the character is ‘(’, it increments the counter and adds it to the result string if it’s not an outermost ‘(’. If the character is ‘)’, it decrements the counter and adds it to the result string if it’s not an outermost ‘)’. After all the iterations, the result string will contain the required parentheses string with all the outermost parentheses removed.

This is a counting problem that needs to track the parenthesis somehow?

Yes, you’re correct. This problem essentially involves counting the open and close parentheses to track the “depth” of the parentheses. If you visualize the parentheses as a sort of hierarchy or tree structure, the outermost parentheses are at the “top level”, or depth zero.

We start with a counter set to 0, representing the top level. Each time we encounter an open parenthesis, we “descend” one level deeper, and each time we encounter a close parenthesis, we “ascend” one level. If we are at a level greater than zero and we encounter a parenthesis (open or close), we know it’s not an outermost parenthesis, so we add it to our result.

By using this counter to keep track of our depth within the parentheses structure, we can identify and ignore the outermost parentheses, solving the problem.

Let’s consider the first example from the problem statement:

s = “(()())(())”

1. Start with an empty string result and a counter at 0.

2. Iterate over each character in the string:

   • ‘(’: counter = 1 (since counter is not greater than 0, we don’t add this to the result)
   • ‘(’: counter = 2 (add this to result, as it’s not an outer parenthesis)
   • ‘)’: counter = 1 (add this to result, as it’s not an outer parenthesis)
   • ‘(’: counter = 2 (add this to result, as it’s not an outer parenthesis)
   • ‘)’: counter = 1 (add this to result, as it’s not an outer parenthesis)
   • ‘)’: counter = 0 (since counter is not greater than 0, we don’t add this to the result)
   • ‘(’: counter = 1 (since counter is not greater than 0, we don’t add this to the result)
   • ‘(’: counter = 2 (add this to result, as it’s not an outer parenthesis)
   • ‘)’: counter = 1 (add this to result, as it’s not an outer parenthesis)
   • ‘)’: counter = 0 (since counter is not greater than 0, we don’t add this to the result)

The result string is “()()()”, which is the string s with the outermost parentheses removed.

Presenting the steps in a table can help clarify the process:

In the end, the result is “()()()” which is the original string with outermost parentheses removed.

Alternative Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

In this class, removeOuterParentheses is a method that takes an input string of parentheses and returns a new string with the outermost parentheses removed from each primitive string in the input. It uses a list res to hold the characters of the resulting string and a variable opened to keep track of the balance of the parentheses. It iterates over each character in the input string, adding the character to res only if it is not an outer parenthesis. Finally, it returns the joined string from the list res.

This function removes the outermost parentheses of every primitive string in the parentheses string S by keeping track of the number of opened parentheses. When it encounters a ‘(’ character, it increments the counter, and when it encounters a ‘)’ character, it decrements the counter. The characters are only added to the result list if they are not outermost parentheses. At the end, the list of characters is joined into a string and returned.

The Python function, removeOuterParentheses, removes the outermost parentheses from every primitive string in the parenthesis string s, and returns the resulting string. A primitive string is a non-empty string that is balanced (i.e., has an equal number of matching opening and closing parentheses) and cannot be divided into two non-empty balanced strings.

Here’s how the function works:

1. It initializes an empty list res to store the characters of the resulting string, and a counter opened to keep track of the balance of parentheses.

2. It then iterates over each character c in the string s.

3. If c is an opening parenthesis and opened is greater than 0, this means c is not part of the outermost parentheses, so it appends c to res.

4. If c is a closing parenthesis and opened is greater than 1, this also means c is not part of the outermost parentheses, so it appends c to res.

5. It then updates opened based on whether c is an opening or closing parenthesis. If c is an opening parenthesis, opened is incremented by 1; if c is a closing parenthesis, opened is decremented by 1.

6. Finally, the function joins the characters in res together into a string and returns this string.

So, for example, if the input string s is "(()())(())", the function will return "()()()". If s is "(()())(())(()(()))", it will return "()()()()(())".

The time complexity of this function is O(n), where n is the length of the string s, because each character in s is processed once. The space complexity is also O(n), because in the worst case, the function might store all characters of s in res.

The opened variable in this solution serves as a counter. It counts the number of opened parentheses we’ve encountered while traversing the string s. This counter helps us distinguish the “outermost” parentheses from those that are not.

Here is a more detailed explanation:

1. The opened counter starts from 0 because initially, we haven’t encountered any parentheses.
2. When we encounter an opening parenthesis '(', we first check if opened is greater than 0. If it is, we know this isn’t an outermost parenthesis, so we add it to our result list res. Then, we increment opened by 1.
3. When we encounter a closing parenthesis ')', we check if opened is greater than 1. If it is, this isn’t an outermost parenthesis, so we add it to res. Then, we decrement opened by 1.

Through this process, we’re effectively “ignoring” the outermost parentheses, only adding those that aren’t the outermost to our result. This gives us the desired result - the string s with all outermost parentheses removed.