# 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.
``````

Example 4:

``````Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"
``````

Constraints:

• `1 <= s.length <= 105`
• `s[i]` is either`'('` , `')'`, or lowercase English letter`.`

``````class Solution {
public:
string minRemoveToMakeValid(string s) {
string res;
stack<int> st;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
if (st.empty()) s[i] = '*';
else st.pop();
}
}
while (!st.empty()) {
s[st.top()] = '*'; st.pop();
}
for (char c : s) {
if (c != '*') res += c;
}
return res;
}
};
``````

``````class Solution {
public:
string minRemoveToMakeValid(string s) {
string res;
int left = 0, right = 0;
for (char c : s) {
if (c == ')') ++right;
}
for (char c : s) {
if (c == '(') {
if (left == right) continue;
++left;
} else if (c == ')') {
--right;
if (left == 0) continue;
--left;
}
res += c;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1249

Minimum Number of Swaps to Make the String Balanced

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/discuss/419402/JavaC%2B%2B-Stack

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/discuss/419466/Constant-Space-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation