1、题目描述：
Leetcode 1249. Minimum Remove to Make Valid Parentheses 移除无效的括号
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
2、解题思路：
使用栈来解决括号匹配的问题
3、代码
class Solution {
public String minRemoveToMakeValid(String s) {
// 使用StringBuilder保存结果
StringBuilder sb = new StringBuilder();
// 记录左括号的位置，用于判断右括号是否匹配
Stack<Integer> stack = new Stack<>();
// 记录需要移除的字符的下标
Set<Integer> toRemove = 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()) {
// 没有左括号匹配，标记为需要移除的字符
toRemove.add(i);
} else {
// 弹出栈顶的左括号
stack.pop();
}
}
}
// 标记未匹配的左括号
while (!stack.isEmpty()) {
toRemove.add(stack.pop());
}
// 构造结果字符串
for (int i = 0; i < s.length(); i++) {
if (!toRemove.contains(i)) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
class Solution {
public String minRemoveToMakeValid(String s) {
// 将字符串转化为字符数组
char[] chars = s.toCharArray();
Stack<Integer> stack = new Stack<>(); // 用栈来存储左括号的下标
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i); // 如果是左括号，将其下标压入栈中
} else if (chars[i] == ')') {
if (!stack.empty()) {
stack.pop(); // 如果是右括号，判断栈是否为空，不为空则弹出栈顶元素
} else {
chars[i] = '*'; // 如果栈为空，则将右括号替换为'*'
}
}
}
while (!stack.empty()) {
chars[stack.pop()] = '*'; // 处理多余的左括号，将其替换为'*'
}
return new String(chars).replaceAll("\\*", ""); // 将所有的'*'替换为空字符
}
}
