[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.

Example 1:
Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:
Input: s = “))((“
Output: “”
Explanation: An empty string is also valid.

Constraints:
1 <= s.length <= 105
s[i] is either’(‘ , ‘)’, or lowercase English letter.

移除无效的括号。

给你一个由 '('、')' 和小写字母组成的字符串 s。 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是 stack 但是这个题跟20题 valid parenthesis 还不太一样，因为不光是判断，而是最后需要返回一个有效的结果。这个题我没有用到 stack 但是用到了 stack 的思想，用一个 open 变量判断到底是左括号多还是右括号多，如果 open 小于0（右括号多）就一定不要再放右括号了。

第一次扫描 input，从左往右，append 其他字符的同时，注意不要多 append 右括号即可，也就是说如果左括号都被抵消完之后又出现右括号，则不要放入结果；第二次从右往左 scan 第一次的结果，但是因为第一次扫描的时候只是控制不能让右括号多于左括号，这时有可能左括号是有多余的，所以在第二次从右往左扫描的时候需要判断如果左括号 left 多了，就不要再加入结果集了。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
	public String minRemoveToMakeValid(String s) {
		StringBuilder sb = new StringBuilder();
		int open = 0;
		for (char c : s.toCharArray()) {
			if (c == '(') {
				open++;
			} else if (c == ')') {
				if (open == 0) {
					continue;
				}
				open--;
			}
			sb.append(c);
		}

		StringBuilder res = new StringBuilder();
		for (int i = sb.length() - 1; i >= 0; i--) {
			if (sb.charAt(i) == '(' && open-- > 0) {
				continue;
			}
			res.append(sb.charAt(i));
		}
		return res.reverse().toString();
	}
}