LeetCode 1249: Minimum Remove to Make Valid Parentheses (Two-Pass Invalid Index Filtering)
LeetCode 1249StringStackToday we solve LeetCode 1249 - Minimum Remove to Make Valid Parentheses.
Source: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
English
Problem Summary
Given a string containing lowercase letters and parentheses, remove the minimum number of parentheses so the final string is valid (balanced and properly ordered).
Key Insight
Only invalid parentheses must be removed: unmatched ) encountered during scan, and leftover unmatched ( after scan. Mark these indices, then rebuild once.
Optimal Algorithm Steps
1) Scan characters left to right.
2) Push index of each ( onto a stack.
3) For each ): if stack non-empty, pop a matching (; otherwise mark this ) index for deletion.
4) After scan, all indices still in stack are unmatched (, mark them for deletion.
5) Build answer by skipping all marked indices.
Complexity Analysis
Time: O(n).
Space: O(n) (stack + marked set).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public String minRemoveToMakeValid(String s) {
Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> remove = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
if (!stack.isEmpty()) stack.pop();
else remove.add(i);
}
}
while (!stack.isEmpty()) {
remove.add(stack.pop());
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!remove.contains(i)) ans.append(s.charAt(i));
}
return ans.toString();
}
}func minRemoveToMakeValid(s string) string {
stack := make([]int, 0)
remove := make(map[int]bool)
for i, ch := range s {
if ch == '(' {
stack = append(stack, i)
} else if ch == ')' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
} else {
remove[i] = true
}
}
}
for _, idx := range stack {
remove[idx] = true
}
out := make([]rune, 0, len(s))
for i, ch := range s {
if !remove[i] {
out = append(out, ch)
}
}
return string(out)
}class Solution {
public:
string minRemoveToMakeValid(string s) {
vector<int> st;
vector<bool> remove(s.size(), false);
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
st.push_back(i);
} else if (s[i] == ')') {
if (!st.empty()) st.pop_back();
else remove[i] = true;
}
}
for (int idx : st) remove[idx] = true;
string ans;
ans.reserve(s.size());
for (int i = 0; i < (int)s.size(); ++i) {
if (!remove[i]) ans.push_back(s[i]);
}
return ans;
}
};class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = []
remove = set()
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
elif ch == ')':
if stack:
stack.pop()
else:
remove.add(i)
remove.update(stack)
return ''.join(ch for i, ch in enumerate(s) if i not in remove)var minRemoveToMakeValid = function(s) {
const stack = [];
const remove = new Set();
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (ch === '(') {
stack.push(i);
} else if (ch === ')') {
if (stack.length > 0) stack.pop();
else remove.add(i);
}
}
while (stack.length > 0) {
remove.add(stack.pop());
}
let ans = '';
for (let i = 0; i < s.length; i++) {
if (!remove.has(i)) ans += s[i];
}
return ans;
};中文
题目概述
给定一个包含小写字母与括号的字符串，要求删除最少数量的括号，使得结果字符串成为合法括号串。
核心思路
只删除无效括号：扫描时遇到无法匹配的 ) 要删；扫描结束后栈里剩下的 ( 也要删。最终按“保留未标记字符”重建答案。
最优算法步骤
1）从左到右扫描字符串。
2）遇到 (，其下标入栈。
3）遇到 )：若栈非空则弹栈配对；否则该 ) 下标记为删除。
4）扫描完后，栈中残留的下标都是未匹配 (，全部标记删除。
5）二次遍历，跳过被标记下标，拼接得到最终合法字符串。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（栈 + 删除标记集合）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public String minRemoveToMakeValid(String s) {
Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> remove = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
if (!stack.isEmpty()) stack.pop();
else remove.add(i);
}
}
while (!stack.isEmpty()) {
remove.add(stack.pop());
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!remove.contains(i)) ans.append(s.charAt(i));
}
return ans.toString();
}
}func minRemoveToMakeValid(s string) string {
stack := make([]int, 0)
remove := make(map[int]bool)
for i, ch := range s {
if ch == '(' {
stack = append(stack, i)
} else if ch == ')' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
} else {
remove[i] = true
}
}
}
for _, idx := range stack {
remove[idx] = true
}
out := make([]rune, 0, len(s))
for i, ch := range s {
if !remove[i] {
out = append(out, ch)
}
}
return string(out)
}class Solution {
public:
string minRemoveToMakeValid(string s) {
vector<int> st;
vector<bool> remove(s.size(), false);
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
st.push_back(i);
} else if (s[i] == ')') {
if (!st.empty()) st.pop_back();
else remove[i] = true;
}
}
for (int idx : st) remove[idx] = true;
string ans;
ans.reserve(s.size());
for (int i = 0; i < (int)s.size(); ++i) {
if (!remove[i]) ans.push_back(s[i]);
}
return ans;
}
};class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = []
remove = set()
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
elif ch == ')':
if stack:
stack.pop()
else:
remove.add(i)
remove.update(stack)
return ''.join(ch for i, ch in enumerate(s) if i not in remove)var minRemoveToMakeValid = function(s) {
const stack = [];
const remove = new Set();
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (ch === '(') {
stack.push(i);
} else if (ch === ')') {
if (stack.length > 0) stack.pop();
else remove.add(i);
}
}
while (stack.length > 0) {
remove.add(stack.pop());
}
let ans = '';
for (let i = 0; i < s.length; i++) {
if (!remove.has(i)) ans += s[i];
}
return ans;
};
Comments