1249. Minimum Remove to Make Valid Parentheses ------M

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 <= 10^5
• s[i] is one of  '(' , ')' and lowercase English letters.

 

A:

Without Stack

先从左向右，如果发现多的 ‘）’ 就删掉

然后再从右向左，如果发现还没有配上的 ‘（’   也立即删掉

class Solution {

public:

string minRemoveToMakeValid(string s) {

auto res = removeMoreRight(s);

return removeMoreLeft(res);

}

private:

string removeMoreRight(string s) {

string res = "";

int cLeft = 0;

for (auto ch : s) {

if (ch == ')') {

if (cLeft > 0) {

--cLeft;

res += ch;

} // else , ignore this )

} else {

res += ch;

if (ch == '(') {

++cLeft;

}

}

}

return res;

}

string removeMoreLeft(string s) {

string res = "";

int cRight = 0;

for (int i = s.size() - 1; i >= 0; i--) {

char ch = s[i];

if (ch == '(') {

if (cRight > 0) {

--cRight;

res += ch; // NOTE, if ch+res, would MLE

} // else , ignore this ()

} else {

res += ch; // NOTE, do not use need add ch as front

if (ch == ')') {

++cRight;

}

}

}

reverse(res.begin(), res.end());

return res;

}

};

ERROR：

     1: 一开始在    removeMoreLeft（），忘记是倒序的，因此忘了 应该是 res = ch + res

     2:  因为其实c++里string会预设大小的，方便后面添加。  可是如果是res = ch + res。 会导致memory limit 

Sol 2:  从左向右，括号如果找不到配对的另一半，则标记

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        vector<bool> deleted(s.size(), false);
        stack<int> S; // stack of (, waiting to be matched.
        for (int i = 0; i < s.size(); i++) {
            char ch = s[i];
            if (ch == '(') {
                S.push(i);
            } else if (ch == ')') {
                if (S.empty()) {
                    deleted[i] = true;
                } else {
                    S.pop();
                }
            }
        }
        while (!S.empty()) {
            deleted[S.top()] = true;
            S.pop();
        }
        string res;
        for (int i = 0; i < s.size(); i++) {
            if (!deleted[i])
                res += s[i];
        }
        return res;
    }
};