In this guide, you will get 1021. Remove Outermost Parentheses LeetCode Solution with the best time and space complexity. The solution to Remove Outermost Parentheses problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 “()()” + “()” + “()(())” = “()()()()(())”.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1021. Remove Outermost Parentheses LeetCode Solution in C++
class Solution {
public:
string removeOuterParentheses(string s) {
string ans;
int opened = 0;
for (const char c : s)
if (c == '(') {
if (++opened > 1)
ans += c;
} else if (--opened > 0) { // c == ')'
ans += c;
}
return ans;
}
}; /* code provided by PROGIEZ */
1021. Remove Outermost Parentheses LeetCode Solution in Java
class Solution {
public String removeOuterParentheses(String s) {
StringBuilder sb = new StringBuilder();
int opened = 0;
for (final char c : s.toCharArray())
if (c == '(') {
if (++opened > 1)
sb.append(c);
} else if (--opened > 0) { // c == ')'
sb.append(c);
}
return sb.toString();
}
} // code provided by PROGIEZ
1021. Remove Outermost Parentheses LeetCode Solution in Python
class Solution:
def removeOuterParentheses(self, s: str) -> str:
ans = []
opened = 0
for c in s:
if c == '(':
opened += 1
if opened > 1:
ans.append(c)
else: # c == ')'
opened -= 1
if opened > 0:
ans.append(c)
return ''.join(ans) # code by PROGIEZ
