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.
Approach:
- Initialize:
stackto track open parentheses.ansto build the final string without outer parentheses.
- Loop through the string:
- If character is
'('- Push to
stack. - Add to
ansonly if stack size > 1 (not outermost).
- Push to
- If character is
')'- Add to
ansonly if stack size > 1 (not outermost). - Pop from
stack.
- Add to
- If character is
- Return the final
ansstring.
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input:
s = "(()())(())(()(()))"
State Transitions:
Initialize: stack = [] ans = ""
i = 0 → s[0] = "("
→ stack.push("(") → stack = ["("]
→ stack.length = 1 → Do NOT add to ans
i = 1 → s[1] = "("
→ stack.push("(") → stack = ["(", "("]
→ stack.length = 2 → ans += "(" → ans = "("
i = 2 → s[2] = ")"
→ stack.length = 2 → ans += ")" → ans = "()"
→ stack.pop() → stack = ["("]
i = 3 → s[3] = ")"
→ stack.length = 1 → Do NOT add to ans
→ stack.pop() → stack = []
i = 4 → s[4] = "("
→ stack.push("(") → stack = ["("]
→ stack.length = 1 → Do NOT add to ans
i = 5 → s[5] = "("
→ stack.push("(") → stack = ["(", "("]
→ stack.length = 2 → ans += "(" → ans = "()("
i = 6 → s[6] = ")"
→ stack.length = 2 → ans += ")" → ans = "()()"
→ stack.pop() → stack = ["("]
i = 7 → s[7] = ")"
→ stack.length = 1 → Do NOT add to ans
→ stack.pop() → stack = []
i = 8 → s[8] = "("
→ stack.push("(") → stack = ["("]
→ stack.length = 1 → Do NOT add to ans
i = 9 → s[9] = "("
→ stack.push("(") → stack = ["(", "("]
→ stack.length = 2 → ans += "(" → ans = "()()("
i = 10 → s[10] = ")"
→ stack.length = 2 → ans += ")" → ans = "()()"
→ stack.pop() → stack = ["("]
i = 11 → s[11] = "("
→ stack.push("(") → stack = ["(", "("]
→ stack.length = 2 → ans += "(" → ans = "()()()("
i = 12 → s[12] = "("
→ stack.push("(") → stack = ["(", "(", "("]
→ stack.length = 3 → ans += "(" → ans = "()()()(("
i = 13 → s[13] = ")"
→ stack.length = 3 → ans += ")" → ans = "()()()(()"
→ stack.pop() → stack = ["(", "("]
i = 14 → s[14] = ")"
→ stack.length = 2 → ans += ")" → ans = "()()()(())"
→ stack.pop() → stack = ["("]
i = 15 → s[15] = ")"
→ stack.length = 1 → Do NOT add to ans
→ stack.pop() → stack = []
Final Output: ()()()(())
Final State: stack = [], ans = "()()()(())"
var removeOuterParentheses = function(s) {
let stack = [];
let ans = "";
for(let i=0; i 1) ? s[i] : "");
} else {
ans += ((stack.length > 1) ? s[i] : "");
stack.pop();
}
}
return ans;
};
def removeOuterParentheses(s: str) -> str:
stack = []
ans = ""
for i in range(len(s)):
if s[i] == '(':
stack.append(s[i])
if len(stack) > 1:
ans += s[i]
else:
if len(stack) > 1:
ans += s[i]
stack.pop()
return ans
import java.util.Stack;
public class Solution {
public String removeOuterParentheses(String s) {
Stack stack = new Stack<>();
StringBuilder ans = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push('(');
if (stack.size() > 1) ans.append('(');
} else {
if (stack.size() > 1) ans.append(')');
stack.pop();
}
}
return ans.toString();
}
}
#include <iostream>
#include <stack>
using namespace std;
string removeOuterParentheses(string s) {
stack stack;
string ans = "";
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
stack.push(s[i]);
if (stack.size() > 1) ans += s[i];
} else {
if (stack.size() > 1) ans += s[i];
stack.pop();
}
}
return ans;
}
#include <stdio.h>
#include <string.h>
char* removeOuterParentheses(char* s) {
static char ans[10000];
int top = -1;
char stack[10000];
int k = 0;
for (int i = 0; s[i]; i++) {
if (s[i] == '(') {
stack[++top] = s[i];
if (top > 0) ans[k++] = s[i];
} else {
if (top > 0) ans[k++] = s[i];
top--;
}
}
ans[k] = '\0';
return ans;
}
using System.Collections.Generic;
using System.Text;
public class Solution {
public string RemoveOuterParentheses(string s) {
Stack stack = new Stack();
StringBuilder ans = new StringBuilder();
for (int i = 0; i < s.Length; i++) {
if (s[i] == '(') {
stack.Push('(');
if (stack.Count > 1) ans.Append('(');
} else {
if (stack.Count > 1) ans.Append(')');
stack.Pop();
}
}
return ans.ToString();
}
}
