Remove Outermost Parentheses — Problem & Solution
Remove Outermost Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Remove Outermost Parentheses is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Stack
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A valid parentheses string is primitive if it is non-empty and cannot be split into two non-empty valid parentheses strings.
Every valid parentheses string s decomposes uniquely into primitive pieces. Remove the outermost parentheses of each piece and return the concatenation of what is left.
Example 1
Input: s = "(()())(())"
Output: ()()()
Explanation: The pieces are "(()())" and "(())"; stripping the outer layer leaves "()()" and "()".
Example 2
Input: s = "(()())(())(()(()))"
Output: ()()()()(())
Example 3
Input: s = "()()"
Output:
Explanation: Both pieces are bare, so nothing survives.
Constraints
1 <= s.length <= 40s is a valid parentheses string.
Hints for Remove Outermost Parentheses
Hint 1
Track the nesting depth as you scan.
Hint 2
An opening bracket at depth 0 and a closing bracket that returns to depth 0 are exactly the outer layer of a primitive piece — skip those.
Hint 3
Careful with the order: increment the depth after deciding about a
(, and decrement before deciding about a).
How to solve Remove Outermost Parentheses
Track the depth. An opening bracket seen at depth 0 and a closing bracket that brings the depth back to 0 form the outer layer of a primitive — skip exactly those.
Approach
- Set
depth = 0. - For
(: append it only ifdepth > 0, then increment. - For
): decrement, then append it only ifdepth > 0.
Why it works
A primitive starts where the depth rises from 0 and ends where it returns to 0; the brackets at those two moments are its outermost pair. Every other bracket is interior to some primitive and is kept.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- The order of test versus update differs for
(and)— increment after deciding, decrement before deciding.
Reference solution
Python
def removeOuterParentheses(s: str) -> str:
out = []
depth = 0
for ch in s:
if ch == "(":
if depth > 0:
out.append(ch)
depth += 1
else:
depth -= 1
if depth > 0:
out.append(ch)
return "".join(out)Java
public static String removeOuterParentheses(String s) {
StringBuilder out = new StringBuilder();
int depth = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
if (depth > 0) out.append('(');
depth++;
} else {
depth--;
if (depth > 0) out.append(')');
}
}
return out.toString();
}C++
string removeOuterParentheses(string s) {
string out = "";
int depth = 0;
for (char c : s) {
if (c == '(') {
if (depth > 0) out += '(';
depth++;
} else {
depth--;
if (depth > 0) out += ')';
}
}
return out;
}JavaScript
var removeOuterParentheses = function(s) {
let out = "";
let depth = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") {
if (depth > 0) out += "(";
depth++;
} else {
depth--;
if (depth > 0) out += ")";
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure