Problem Statement:
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.
Examples:
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 2:
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.
Second Approach: Without Stack
- Initialize: a counter
levelto-1and an empty stringans. - Traverse each character of the string
s. - If the character is
'('- Increment
level. - If
levelis not0, append'('toans.
- Increment
- If the character is
')'- If
levelis not0, append')'to ans. - Then decrement
level.
- If
- Return the final
ansstring.
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input:
s = "(()())(())(()(()))"
State Transitions:
Initialize: level = -1, ans = ""
i = 0 → s[0] = "("
→ ++level → level = 0
→ level is 0 → Do NOT add to ans
i = 1 → s[1] = "("
→ ++level → level = 1
→ level is non-zero → ans += "(" → ans = "("
i = 2 → s[2] = ")"
→ level is non-zero → ans += ")" → ans = "()"
→ --level → level = 0
i = 3 → s[3] = ")"
→ level is 0 → Do NOT add to ans
→ --level → level = -1
i = 4 → s[4] = "("
→ ++level → level = 0
→ level is 0 → Do NOT add to ans
i = 5 → s[5] = "("
→ ++level → level = 1
→ level is non-zero → ans += "(" → ans = "()("
i = 6 → s[6] = ")"
→ level is non-zero → ans += ")" → ans = "()()"
→ --level → level = 0
i = 7 → s[7] = ")"
→ level is 0 → Do NOT add to ans
→ --level → level = -1
i = 8 → s[8] = "("
→ ++level → level = 0
→ level is 0 → Do NOT add to ans
i = 9 → s[9] = "("
→ ++level → level = 1
→ level is non-zero → ans += "(" → ans = "()()("
i = 10 → s[10] = ")"
→ level is non-zero → ans += ")" → ans = "()()()"
→ --level → level = 0
i = 11 → s[11] = "("
→ ++level → level = 1
→ level is non-zero → ans += "(" → ans = "()()()("
i = 12 → s[12] = "("
→ ++level → level = 2
→ level is non-zero → ans += "(" → ans = "()()()(("
i = 13 → s[13] = ")"
→ level is non-zero → ans += ")" → ans = "()()()(()"
→ --level → level = 1
i = 14 → s[14] = ")"
→ level is non-zero → ans += ")" → ans = "()()()(())"
→ --level → level = 0
i = 15 → s[15] = ")"
→ level is 0 → Do NOT add to ans
→ --level → level = -1
Final Output: ()()()(())
Final State: level = -1, ans = "()()()(())"
var removeOuterParentheses = function(s) {
let level = -1;
let ans = "";
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") {
++level;
ans += (level ? s[i] : "");
} else {
ans += (level ? s[i] : "");
--level;
}
}
return ans;
};
def removeOuterParentheses(s: str) -> str:
level = -1
ans = ""
for i in range(len(s)):
if s[i] == "(":
level += 1
ans += s[i] if level else ""
else:
ans += s[i] if level else ""
level -= 1
return ans
public class Solution {
public String removeOuterParentheses(String s) {
int level = -1;
StringBuilder ans = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(') {
++level;
if(level != 0) ans.append(s.charAt(i));
} else {
if(level != 0) ans.append(s.charAt(i));
--level;
}
}
return ans.toString();
}
}
#include <string>
using namespace std;
string removeOuterParentheses(string s) {
int level = -1;
string ans = "";
for(int i = 0; i < s.length(); i++) {
if(s[i] == '(') {
++level;
ans += (level ? s[i] : '\0');
} else {
ans += (level ? s[i] : '\0');
--level;
}
}
ans.erase(remove(ans.begin(), ans.end(), '\0'), ans.end());
return ans;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* removeOuterParentheses(char* s) {
int level = -1;
int len = strlen(s);
char* ans = (char*)malloc(len + 1);
int index = 0;
for(int i = 0; i < len; i++) {
if(s[i] == '(') {
++level;
if(level) ans[index++] = s[i];
} else {
if(level) ans[index++] = s[i];
--level;
}
}
ans[index] = '\0';
return ans;
}
public class Solution {
public string RemoveOuterParentheses(string s) {
int level = -1;
string ans = "";
for(int i = 0; i < s.Length; i++) {
if(s[i] == '(') {
++level;
ans += (level != 0) ? s[i].ToString() : "";
} else {
ans += (level != 0) ? s[i].ToString() : "";
--level;
}
}
return ans;
}
}
