# 1021. Remove Outermost Parentheses

## 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 = P1 + P2 + ... + Pk, where Pi 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: s = "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".


Example 2:

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


Example 3:

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


Constraints:

• 1 <= s.length <= 105
• s[i] is either '(' or ')'.
• s is a valid parentheses string.

## Solutions

• class Solution {
public String removeOuterParentheses(String s) {
StringBuilder ans = new StringBuilder();
int cnt = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == '(') {
if (++cnt > 1) {
ans.append(c);
}
} else {
if (--cnt > 0) {
ans.append(c);
}
}
}
return ans.toString();
}
}

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

• class Solution:
def removeOuterParentheses(self, s: str) -> str:
ans = []
cnt = 0
for c in s:
if c == '(':
cnt += 1
if cnt > 1:
ans.append(c)
else:
cnt -= 1
if cnt > 0:
ans.append(c)
return ''.join(ans)


• func removeOuterParentheses(s string) string {
ans := []rune{}
cnt := 0
for _, c := range s {
if c == '(' {
cnt++
if cnt > 1 {
ans = append(ans, c)
}
} else {
cnt--
if cnt > 0 {
ans = append(ans, c)
}
}
}
return string(ans)
}

• function removeOuterParentheses(s: string): string {
let res = '';
let depth = 0;
for (const c of s) {
if (c === '(') {
depth++;
}
if (depth !== 1) {
res += c;
}
if (c === ')') {
depth--;
}
}
return res;
}


• impl Solution {
pub fn remove_outer_parentheses(s: String) -> String {
let mut res = String::new();
let mut depth = 0;
for c in s.chars() {
if c == '(' {
depth += 1;
}
if depth != 1 {
res.push(c);
}
if c == ')' {
depth -= 1;
}
}
res
}
}