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

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

Analysis

In order to identify which parenthesis should be included in our return string, we need to check two cases:

1. If the current open parenthesis is the first parenthesis in the block of the decomposition, we should not add it. This means the current number of unmatched pairs in the block is 1.
2. If the current close parenthesis is the last parenthesis in the block of the decomposition, we should not add it. This means the current number of unmatched pairs in the block is 0.

Let's walk through an example:

The leftmost column represents the current processing parenthesis.

For "(()(()))":
(    (|()(())): we have 1 unmatched pair -> "" don't do anything here
(    ((|)(())): we have 2 unmatched pair -> "("
)    (()|(())): we have 1 unmatched pair -> "()"
(    (()(|())): we have 2 unmatched pair -> "()("
(    (()((|))): we have 3 unmatched pair -> "()(("
)    (()(()|)): we have 2 unmatched pair -> "()(()"
)    (()(())|): we have 1 unmatched pair -> "()(())"
)    (()(()))|: we have 0 unmatched pair -> "()(())" don't do anything here

From this example, we can see that all we need is to count the number of unmatched pairs as well as the current processing parenthesis.

Time: $O(n)$

Space: $O(1)$

Code

class Solution {
public:
    string removeOuterParentheses(string S) {
        string res;
        int cnt = 0;
        for (char& c : S) {
            if (c == '(' && ++cnt != 1)
                res += c;
            if (c == ')' && --cnt != 0)
                res += c;
        }
        return res;
    }
};

Note that since the input is always valid (no mismatch), we can just use != instead of >= to check the unmatched pairs.