Practice › Strings
Remove Outermost Parentheses
Easy · Strings · Asked at Amazon, Google, TCS, Infosys
The string is a valid parentheses string. Split it into its primitive parts (non-empty valid strings that cannot be split further) and remove the outermost pair of each part. Print the result.
Input
A single string s of ( and ).
Output
The string after removing the outermost parentheses. It is guaranteed not to be empty.
Constraints
- 2 ≤ |s| ≤ 10^5
sis a valid parentheses string
Track the depth: print a "(" only if the depth was already > 0 before it, and a ")" only if the depth stays > 0 after it.
Example 1
Input
(()())(())
Output
()()()
Example 2
Input
(()())(())(()(()))
Output
()()()()(())
Hints
- Keep a depth counter. A primitive part ends whenever the depth returns to 0.
- The outermost "(" is the one seen at depth 0; the outermost ")" is the one that brings depth back to 0. Skip exactly those.
Approach
Scan once with depth. For "(": append it only if depth > 0, then increment. For ")": decrement first, then append only if depth > 0. This drops exactly the first and last bracket of every primitive part without splitting the string explicitly.
Complexity: O(n) time · O(n) space for the output
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, out;
cin >> s;
int depth = 0;
for (char c : s) {
if (c == '(') {
if (depth > 0) out += c;
depth++;
} else {
depth--;
if (depth > 0) out += c;
}
}
cout << out << "\n";
return 0;
}Python solution
s = input().strip()
out, depth = [], 0
for c in s:
if c == "(":
if depth > 0:
out.append(c)
depth += 1
else:
depth -= 1
if depth > 0:
out.append(c)
print("".join(out))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
StringBuilder out = new StringBuilder();
int depth = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
if (depth > 0) out.append(c);
depth++;
} else {
depth--;
if (depth > 0) out.append(c);
}
}
System.out.println(out);
}
}Solve Remove Outermost Parentheses online · All practice problems