Minimum Remove to Make Valid Parentheses
Minimum Remove to Make Valid Parentheses is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (two passes with a counter), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from stack of unmatched indices up.
Problem
You are given a string s made of lowercase letters and the brackets '(' and ')'.
Delete as few brackets as possible so that the remaining string is valid, and return it. A string is valid when every '(' has a matching ')' after it and every ')' closes an earlier '('; letters are ignored for this check and are never removed. A string with no brackets (including the empty string) is valid.
If several answers remove the same smallest number of brackets, return any of them.
Examples
Example 1
- Input
s = "x(y)z)"- Output
"x(y)z"- Why
- The last ')' has nothing to close, so it is the one removal needed.
Example 2
- Input
s = "))(("- Output
""- Why
- No bracket can be matched, so all four go and the empty string is left.
Example 3
- Input
s = "(a(b)c"- Output
"(ab)c"- Why
- One '(' is unmatched. Dropping either '(' works, so "a(b)c" is accepted too.
Constraints
1 <= s.length <= 10^5s[i]is'(',')'or a lowercase English letter.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Stack of unmatched indices | O(n) | O(n) |
| Optimal (two passes with a counter) | O(n) | O(n) |
1Stack of unmatched indices
O(n)Each character is pushed and popped at most once, then copied once.O(n)The stack, the mark array and the output builder are all up to n long.Push the index of every '(' on a stack. On ')', pop the matching '(' if there is one; otherwise mark this ')' for removal. Indices left on the stack at the end are unmatched '(' and are marked too. Build the result from the unmarked characters.
- remove = boolean[n]; stack = empty.
- For each i: '(' → push i. ')' → if the stack is empty, remove[i] = true, else pop.
- Mark every index still on the stack.
- Append every character whose index is not marked.
class Solution {
public String minRemoveToMakeValid(String s) {
int n = s.length();
boolean[] remove = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == '(') {
stack.push(i);
} else if (ch == ')') {
if (stack.isEmpty()) {
remove[i] = true;
} else {
stack.pop();
}
}
}
while (!stack.isEmpty()) {
remove[stack.pop()] = true;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
if (!remove[i]) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
n = len(s)
remove = [False] * n
stack = []
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
elif ch == ')':
if not stack:
remove[i] = True
else:
stack.pop()
for i in stack:
remove[i] = True
return "".join(s[i] for i in range(n) if not remove[i])class Solution {
public:
string minRemoveToMakeValid(string s) {
int n = s.size();
vector<bool> remove(n, false);
vector<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
st.push_back(i);
} else if (s[i] == ')') {
if (st.empty()) remove[i] = true;
else st.pop_back();
}
}
for (int i : st) remove[i] = true;
string out;
for (int i = 0; i < n; i++)
if (!remove[i]) out += s[i];
return out;
}
};function minRemoveToMakeValid(s) {
const n = s.length;
const remove = new Array(n).fill(false);
const stack = [];
for (let i = 0; i < n; i++) {
if (s[i] === '(') {
stack.push(i);
} else if (s[i] === ')') {
if (stack.length === 0) remove[i] = true;
else stack.pop();
}
}
for (const i of stack) remove[i] = true;
const out = [];
for (let i = 0; i < n; i++) if (!remove[i]) out.push(s[i]);
return out.join('');
}2Optimal (two passes with a counter)
O(n)Two linear passes and one reversal.O(n)Only counters besides the output builders, which are needed anyway.A counter is enough. The forward pass keeps a ')' only while some '(' is open, which removes every unmatchable ')'. After it, open '(' are still unmatched; the backward pass skips that many '(' starting from the right end. Keeping the leftmost ones is always safe, since each surviving '(' still has its ')' after it.
- Forward: open = 0. Append letters; append '(' and do open++; append ')' only if open > 0 (then open--).
- Backward over that result: skip the last
open'(' characters, keep everything else. - Reverse the kept characters (they were collected right to left).
class Solution {
public String minRemoveToMakeValid(String s) {
StringBuilder first = new StringBuilder();
int open = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
open++;
first.append(ch);
} else if (ch == ')') {
if (open > 0) {
open--;
first.append(ch);
}
} else {
first.append(ch);
}
}
StringBuilder result = new StringBuilder();
for (int i = first.length() - 1; i >= 0; i--) {
char ch = first.charAt(i);
if (ch == '(' && open > 0) {
open--;
continue;
}
result.append(ch);
}
return result.reverse().toString();
}
}class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
first = []
open_count = 0
for ch in s:
if ch == '(':
open_count += 1
first.append(ch)
elif ch == ')':
if open_count > 0:
open_count -= 1
first.append(ch)
else:
first.append(ch)
result = []
for ch in reversed(first):
if ch == '(' and open_count > 0:
open_count -= 1
continue
result.append(ch)
return "".join(reversed(result))class Solution {
public:
string minRemoveToMakeValid(string s) {
string first;
int open = 0;
for (char ch : s) {
if (ch == '(') {
open++;
first += ch;
} else if (ch == ')') {
if (open > 0) {
open--;
first += ch;
}
} else {
first += ch;
}
}
string result;
for (int i = (int)first.size() - 1; i >= 0; i--) {
char ch = first[i];
if (ch == '(' && open > 0) {
open--;
continue;
}
result += ch;
}
reverse(result.begin(), result.end());
return result;
}
};function minRemoveToMakeValid(s) {
const first = [];
let open = 0;
for (const ch of s) {
if (ch === '(') {
open++;
first.push(ch);
} else if (ch === ')') {
if (open > 0) {
open--;
first.push(ch);
}
} else {
first.push(ch);
}
}
const result = [];
for (let i = first.length - 1; i >= 0; i--) {
const ch = first[i];
if (ch === '(' && open > 0) {
open--;
continue;
}
result.push(ch);
}
return result.reverse().join('');
}Edge cases to test
- A string with no brackets at all (return it unchanged)
- Only closing brackets, or only opening brackets
- A ')' that appears before any '('
- Several equally short answers: any one of them is accepted
Hints
Hint 1
Scanning left to right with a counter of open brackets, a ')' seen while the counter is 0 can never be matched. It must be removed.
Hint 2
After that scan, the '(' that are still open at the end must also be removed. Which ones? Remember where they were.
Hint 3
Alternatively, scan once forward to drop bad ')', then once backward (with the roles swapped) to drop bad '('.
FAQ
What is the best time complexity for Minimum Remove to Make Valid Parentheses?
Optimal (two passes with a counter) runs in O(n) time and O(n) extra space. Two linear passes and one reversal.
Which pattern does Minimum Remove to Make Valid Parentheses use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Minimum Remove to Make Valid Parentheses?
Yes. Stack of unmatched indices takes O(n) time and O(n) space. Push the index of every '(' on a stack.
Which edge cases should I test for Minimum Remove to Make Valid Parentheses?
A string with no brackets at all (return it unchanged); Only closing brackets, or only opening brackets; A ')' that appears before any '('; Several equally short answers: any one of them is accepted.