Algorithm
Problem Name: 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 = 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')'.sis a valid parentheses string.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String removeOuterParentheses(String S) {
Stack stack = new Stack<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
if (stack.isEmpty() && c == '(') {
stack.push(c);
continue;
}
if (stack.size() == 1 && c == ')') {
stack.pop();
continue;
}
if (c == '(') {
stack.push(c);
}
else {
stack.pop();
}
sb.append(c);
}
return sb.toString();
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
/**
* @param {string} S
* @return {string}
*/
const removeOuterParentheses = function(S) {
let onum = 0
let oidx = 0
let cnum = 0
let cidx = 0
let res = ''
const arr = S.split('')
for(let i = 0, len = S.length; i < len; i++) {
if(S[i] === '(') onum++
if(S[i] === ')') cnum++
if(onum === cnum) {
res += arr.slice(oidx + 1, oidx + cnum * 2 - 1).join('')
onum = 0
cnum = 0
oidx = i+1
}
}
return res
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def removeOuterParentheses(self, S: str) -> str:
l = r = 0
res = cur = ''
for s in S:
cur += s
l += s == '('
r += s == ')'
if l == r:
res += cur[1:-1]
cur = ''
return res
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System.Text;
namespace LeetCode
{
public class _1021_RemoveOutermostParentheses
{
public string RemoveOuterParentheses(string S)
{
if (S.Length < = 2) return string.Empty;
var sb = new StringBuilder();
var count = 0;
var start = 0;
for (int i = 0; i < S.Length; i++)
{
count += S[i] == '(' ? 1 : -1;
if (count == 0)
{
if (i - start - 1 > 0)
sb.Append(S.Substring(start + 1, i - start - 1));
start = i + 1;
}
}
return sb.ToString();
}
}
}
Input
Output