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 to be included inside our return string, we need to check two cases:

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

Let's walk through an example:

The left most column represents the current processing parthesis

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.

---

Last update: March 31, 2022