# 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

``````class Solution {
public:
string removeOuterParentheses(string S) {
string res = "";
int cnt = 0, start = 0, n = S.size();
for (int i = 0; i < n; ++i) {
(S[i] == '(') ? ++cnt : --cnt;
if (cnt != 0) continue;
res += S.substr(start + 1, i - start - 1);
start = i + 1;
}
return res;
}
};
``````

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1021

Valid Parentheses

Valid Parenthesis String

Remove Invalid Parentheses

Longest Valid Parentheses

https://leetcode.com/problems/remove-outermost-parentheses/

https://leetcode.com/problems/remove-outermost-parentheses/discuss/270022/JavaC%2B%2BPython-Count-Opened-Parenthesis

https://leetcode.com/problems/remove-outermost-parentheses/discuss/270566/My-Java-3ms-Straight-Forward-Solution-or-Beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation