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 <= 105s[i] is either '(' or ')'.s is a valid parentheses string.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
| 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)
if c == ')':
cnt -= 1
return ''.join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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 == '(') {
++cnt;
}
if (cnt > 1) {
ans.append(c);
}
if (c == ')') {
--cnt;
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
string removeOuterParentheses(string s) {
string ans;
int cnt = 0;
for (char& c : s) {
if (c == '(') {
++cnt;
}
if (cnt > 1) {
ans.push_back(c);
}
if (c == ')') {
--cnt;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func removeOuterParentheses(s string) string {
ans := []rune{}
cnt := 0
for _, c := range s {
if c == '(' {
cnt++
}
if cnt > 1 {
ans = append(ans, c)
}
if c == ')' {
cnt--
}
}
return string(ans)
}
|
