1021. Remove Outermost Parentheses (Python)

Related Topic

Stack.

Description

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_1 + P_2 + … + 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.

Sample I/O

Example 1

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

Example 2

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

Example 3

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

Note

1. S.length <= 10000
2. S[i] is “(“ or “)”
3. S is a valid parentheses string

Methodology

One of the readable solution will be use stack to operate the string, append “(“ when meet “(“ and pop “(“ when meet “)”. We also need a set to store the indexes that need to remove. After pop, once the stack is empty we add the last value index and current value index into set. Then we iterate the string again. Skip those index in set and concatenate others character to the answer.

There is a better performance solution that you do not need a set. The idea is same. Instand of using set to store the index to remove, we can directly use list slice to append the string to answer.

stack + set

    def removeOuterParentheses(self, S: str) -> str:
        stack = []
        index_remove=set()
        res=""
        for i, v in enumerate(S):
            if v == "(":
                stack.append(i)
            else:
                left_index = stack.pop()
                if not stack:
                    index_remove.add(left_index)
                    index_remove.add(i)
        for i, v in enumerate(S):
            if i not in index_remove:
                res+=v
        return res

BigO

We iterate the list twice so the total cost will be O(2n)

stack + list slicing

    def removeOuterParentheses(self, S: str) -> str:
        size = len(S)
        index = 0
        stack = []
        res = ""
        while index<size:
            if S[index] == '(':
                stack.append(index)
            elif S[index] == ')':
                index_remove = stack.pop()
                if not stack:
                    res += S[index_remove+1:index]
            index+= 1
        return res

BigO

We iterate the list twice so the total cost will be roughly O(2n)