Minimum Remove to Make Valid Parentheses — Solution
Minimum Remove to Make Valid Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Remove to Make Valid Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Strings, Stack
- Asked at: Amazon, Google, Meta, Bloomberg
- 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
Given a string s of lowercase letters and parentheses, remove the minimum number of parentheses so that the result is valid.
A string is valid if the brackets match and the letters are left untouched. If several answers have the same minimal length, any of them is accepted; return the one produced by removing unmatched brackets and keeping everything else in place.
Example 1
Input: s = "lee(t(c)o)de)"
Output: lee(t(c)o)de
Explanation: The last ')' has no partner.
Example 2
Input: s = "a)b(c)d"
Output: ab(c)d
Example 3
Input: s = "))(("
Output:
Constraints
1 <= s.length <= 40s consists of lowercase English letters, '(' and ')'.
Hints for Minimum Remove to Make Valid Parentheses
Hint 1
Do one pass keeping a stack of the indices of unmatched
(.Hint 2
A
)with an empty stack is unmatched — mark it for deletion immediately.Hint 3
Whatever indices remain on the stack at the end are unmatched
(— mark those too, then rebuild the string.
How to solve Minimum Remove to Make Valid Parentheses
One pass with a stack of unmatched ( indices: a ) with an empty stack is marked for removal on the spot, and every index left on the stack is removed at the end.
Approach
- Walk the string; push indices of
(, pop on)when possible, else mark the). - Mark every index remaining on the stack.
- Rebuild the string from the unmarked characters.
Why it works
The greedy matching pairs each ) with the nearest available (; the brackets left unmatched are exactly the minimum set whose removal balances the string.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Letters are never removed; only the marked brackets are dropped.
Reference solution
Python
def minRemoveToMakeValid(s: str) -> str:
keep = [True] * len(s)
open_idx = []
for i, ch in enumerate(s):
if ch == "(":
open_idx.append(i)
elif ch == ")":
if open_idx:
open_idx.pop()
else:
keep[i] = False
for i in open_idx:
keep[i] = False
return "".join(ch for ch, k in zip(s, keep) if k)Java
public static String minRemoveToMakeValid(String s) {
boolean[] keep = new boolean[s.length()];
Arrays.fill(keep, true);
Deque<Integer> openIdx = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
openIdx.push(i);
} else if (c == ')') {
if (!openIdx.isEmpty()) openIdx.pop();
else keep[i] = false;
}
}
for (int i : openIdx) keep[i] = false;
StringBuilder out = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (keep[i]) out.append(s.charAt(i));
}
return out.toString();
}C++
string minRemoveToMakeValid(string s) {
vector<bool> keep(s.size(), true);
vector<int> openIdx;
for (int i = 0; i < (int) s.size(); i++) {
if (s[i] == '(') openIdx.push_back(i);
else if (s[i] == ')') {
if (!openIdx.empty()) openIdx.pop_back();
else keep[i] = false;
}
}
for (int i : openIdx) keep[i] = false;
string out;
for (int i = 0; i < (int) s.size(); i++) {
if (keep[i]) out.push_back(s[i]);
}
return out;
}JavaScript
var minRemoveToMakeValid = function(s) {
const keep = [];
for (let i = 0; i < s.length; i++) keep.push(true);
const openIdx = [];
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (c === "(") openIdx.push(i);
else if (c === ")") {
if (openIdx.length > 0) openIdx.pop();
else keep[i] = false;
}
}
for (let i = 0; i < openIdx.length; i++) keep[openIdx[i]] = false;
let out = "";
for (let i = 0; i < s.length; i++) {
if (keep[i]) out += s.charAt(i);
}
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