1021. Remove Outermost Parentheses

Problem 1021

https://leetcode.com/problems/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 = 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.

Example 1:

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

Solution

python

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

C++

class Solution {
public:
    string removeOuterParentheses(string S) {
        string out;
        int count = 0;
        for (char s : S){
            if(s == '(' && count++ > 0 ) out += s;
            if(s == ')' && count-- > 1 ) out += s;
        }
        return out;
    }
};