python C++字串deque解Leetcode 1249 Minimum Remove to Make Valid Parentheses

python C++字串deque解Leetcode 1249  Minimum Remove to Make Valid Parentheses

連續幾天都是含括號的字串問題Leetcode 1249. Minimum Remove to Make Valid Parentheses，都提示用stack其實不用，走訪兩次就好，一次去掉多的 ')' ，第二反向去掉多的 '(' ；選用適當的容器，字串、deque就得解了，最快的C++解請進

---

Leetcode 1249. Minimum Remove to Make Valid Parentheses has been a problem with strings containing parentheses for several days in a row. It all prompts that stack is not necessary. Just visit twice. One time to remove too many ')'s, and the second time in reverse to remove too many '('s ;Choose an appropriate container, and the string and deque will have to be solved.

[codes on Leetcode]https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/solutions/4980210/deque-string-vs-string-reverse-vs-string-3ms-beats-98-08/

[Leetcode程式]https://www.youtube.com/watch?v=XpO9wcI8KAg&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

#pragma GCC optimize("O3", "unroll-loops")
class Solution {
public:
    string minRemoveToMakeValid(string& s) {
        int p=0, n=s.size();
        for(int i=n-1; i>=0; i--){
            char& c=s[i];
            p+=(c=='(')-(c==')');
            if (p>0) c='@', p=0;
        }
        int sz=n;
        p=0;
        for(int i=0, j=0; i=0) s[j++]=c;
            else sz--, p=0;
        }
        s.resize(sz, '\0');
        return s;
    }
};


auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();