1249. 移除无效的括号
题目描述
输入字符串 s，由 '('、')' 和小写字母组成。
有效括号串的定义：空串或只含小写字母的串是有效的；两个有效串拼接后有效；有效串外面套一对括号也有效。
从 s 中删除尽量少的括号（位置任选，字母不能删），使剩下的字符串有效。返回任意一个满足要求的结果。
示例 1
输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de"
解释：删掉末尾多余的 )；删除其他位置的右括号也可行。
示例 2
输入：s = "a)b(c)d" 输出："ab(c)d"
解释：删掉第一个 )。
示例 3
输入：s = "))(("
输出：""解释：四个括号都无法配对，全部删除后得到空串。
数据范围
1 <= s.length <= 10^5s[i]是'('、')'或小写英文字母。
解题思路：栈记录未匹配的左括号
括号无效只有两种：到达时前面没有未配对 ( 的 )，以及扫完后仍未配对的 (。用栈存未配对 ( 的下标：遇到 ( 压入；遇到 ) 如果栈非空就弹出配对，否则这个 ) 必须删除。扫描结束后栈里剩下的 ( 也全部删除。每个被删括号都是不得不删的，所以删除数最少。
为什么正确
扫到位置 i 时，栈中是前缀里尚未配对的 ( 的下标，已标记删除的 ) 在任何方案中都无法配对。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
只处理多余的 ) 是不够的：扫描结束后栈里剩下的 ( 也要删掉；栈里必须存下标而不是计数，才知道删哪一个。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
chars = list(s)
stack = []
for i, c in enumerate(chars):
if c == '(':
stack.append(i)
elif c == ')':
if stack:
stack.pop()
else:
chars[i] = ''
for i in stack:
chars[i] = ''
return ''.join(chars)class Solution {
public String minRemoveToMakeValid(String s) {
char[] chars = s.toCharArray();
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i);
} else if (chars[i] == ')') {
if (!stack.isEmpty()) {
stack.pop();
} else {
chars[i] = '*';
}
}
}
for (int i : stack) {
chars[i] = '*';
}
StringBuilder sb = new StringBuilder();
for (char c : chars) if (c != '*') sb.append(c);
return sb.toString();
}
}class Solution {
public:
string minRemoveToMakeValid(string s) {
string chars = s;
vector<int> stack;
for (int i = 0; i < (int)chars.size(); i++) {
if (chars[i] == '(') {
stack.push_back(i);
} else if (chars[i] == ')') {
if (!stack.empty()) {
stack.pop_back();
} else {
chars[i] = '*';
}
}
}
for (int i : stack) {
chars[i] = '*';
}
string res;
for (char c : chars) if (c != '*') res += c;
return res;
}
};func minRemoveToMakeValid(s string) string {
chars := []byte(s)
stack := []int{}
for i, c := range chars {
if c == '(' {
stack = append(stack, i)
} else if c == ')' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
} else {
chars[i] = '*'
}
}
}
for _, i := range stack {
chars[i] = '*'
}
res := []byte{}
for _, c := range chars {
if c != '*' {
res = append(res, c)
}
}
return string(res)
}var minRemoveToMakeValid = function(s) {
const chars = s.split('');
const stack = [];
for (let i = 0; i < chars.length; i++) {
if (chars[i] === '(') {
stack.push(i);
} else if (chars[i] === ')') {
if (stack.length) {
stack.pop();
} else {
chars[i] = '';
}
}
}
for (const i of stack) {
chars[i] = '';
}
return chars.join('');
};function minRemoveToMakeValid(s: string): string {
const chars = s.split('');
const stack: number[] = [];
for (let i = 0; i < chars.length; i++) {
if (chars[i] === '(') {
stack.push(i);
} else if (chars[i] === ')') {
if (stack.length) {
stack.pop();
} else {
chars[i] = '';
}
}
}
for (const i of stack) {
chars[i] = '';
}
return chars.join('');
}其他解法
栈方法一遍就确定哪些括号要删：多余的 ) 在扫描时发现，多余的 ( 是最后留在栈里的下标；两次扫描法利用左右对称性，正向删 )、反向删 (，只需要计数器。
解法 2：两次扫描 + 计数 时间 O(n)，空间 O(n)
不记录下标，只用一个计数器 bal。第一次从左到右扫描：遇到 ( 时 bal 加 1；遇到 ) 时若 bal 为 0，说明它没有能配对的左括号，直接丢弃，否则 bal 减 1。这一遍删掉了所有多余的 )。第二次对结果从右到左扫描，把两种括号的角色对调：遇到 ) 计数，遇到没有配对的 ( 就丢弃。两遍之后剩下的括号全部合法。
用计数器代替下标栈，思路左右对称、容易证明，也容易推广到“只问至少要删几个”的问题。需要扫描两遍并做一次反转。
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
first = []
bal = 0
for c in s:
if c == '(':
bal += 1
elif c == ')':
if bal == 0:
continue
bal -= 1
first.append(c)
res = []
bal = 0
for c in reversed(first):
if c == ')':
bal += 1
elif c == '(':
if bal == 0:
continue
bal -= 1
res.append(c)
return ''.join(reversed(res))class Solution {
public String minRemoveToMakeValid(String s) {
StringBuilder first = new StringBuilder();
int bal = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
bal++;
} else if (c == ')') {
if (bal == 0) continue;
bal--;
}
first.append(c);
}
StringBuilder res = new StringBuilder();
bal = 0;
for (int i = first.length() - 1; i >= 0; i--) {
char c = first.charAt(i);
if (c == ')') {
bal++;
} else if (c == '(') {
if (bal == 0) continue;
bal--;
}
res.append(c);
}
return res.reverse().toString();
}
}class Solution {
public:
string minRemoveToMakeValid(string s) {
string first;
int bal = 0;
for (char c : s) {
if (c == '(') {
bal++;
} else if (c == ')') {
if (bal == 0) continue;
bal--;
}
first += c;
}
string res;
bal = 0;
for (int i = (int)first.size() - 1; i >= 0; i--) {
char c = first[i];
if (c == ')') {
bal++;
} else if (c == '(') {
if (bal == 0) continue;
bal--;
}
res += c;
}
reverse(res.begin(), res.end());
return res;
}
};func minRemoveToMakeValid(s string) string {
first := []byte{}
bal := 0
for i := 0; i < len(s); i++ {
c := s[i]
if c == '(' {
bal++
} else if c == ')' {
if bal == 0 {
continue
}
bal--
}
first = append(first, c)
}
res := []byte{}
bal = 0
for i := len(first) - 1; i >= 0; i-- {
c := first[i]
if c == ')' {
bal++
} else if c == '(' {
if bal == 0 {
continue
}
bal--
}
res = append(res, c)
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return string(res)
}var minRemoveToMakeValid = function(s) {
const first = [];
let bal = 0;
for (const c of s) {
if (c === '(') {
bal++;
} else if (c === ')') {
if (bal === 0) continue;
bal--;
}
first.push(c);
}
const res = [];
bal = 0;
for (let i = first.length - 1; i >= 0; i--) {
const c = first[i];
if (c === ')') {
bal++;
} else if (c === '(') {
if (bal === 0) continue;
bal--;
}
res.push(c);
}
return res.reverse().join('');
};function minRemoveToMakeValid(s: string): string {
const first: string[] = [];
let bal = 0;
for (const c of s) {
if (c === '(') {
bal++;
} else if (c === ')') {
if (bal === 0) continue;
bal--;
}
first.push(c);
}
const res: string[] = [];
bal = 0;
for (let i = first.length - 1; i >= 0; i--) {
const c = first[i];
if (c === ')') {
bal++;
} else if (c === '(') {
if (bal === 0) continue;
bal--;
}
res.push(c);
}
return res.reverse().join('');
}