deque +string vs string+ reverse vs string||6ms Beats 99.97%
IntuitionA several pass solution. 1st pass is to remove the redundant ')'; 2nd pass is an inverse trasversal which removes the redundant '('.Later try other app
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
A several pass solution. 1st pass is to remove the redundant ')'; 2nd pass is an inverse trasversal which removes the redundant '('.

Later try other approaches.
2nd approach uses just string & reverse.
3rd approach uses only string with SC O(1); thanks to the suggestion by @ Sergei, 1st pass is backward, 2nd pass is a forward trasversal. The C++ implementation :6ms Beats 99.97%, C implementation is faster only 2ms & & beats 98.08%
# Approach
<!-- Describe your approach to solving the problem. -->
[Please turn on English subtitles if necessary]
[https://youtu.be/527BNZYm6aE?si=h0hrcDHFx-Q3t6Vl](https://youtu.be/527BNZYm6aE?si=h0hrcDHFx-Q3t6Vl)
Since the depth of any char c in a VPS=(# of `'('` before c)-(# of '`)'` before c),
transverse do the following
```
p+=(c=='(')-(c==')');//count the current depth for the char c
```
1. 1st pass needs a container like stack, a string `t` is good for this task; when p>=0, the parenthesis string is valid by `push_back(c)`, otherwise reset p=0.
2. 2nd pass needs a container which has O(1)-time for `push_front`( `appendleft` in Python); a deque `q` is used for this task. When p<=0, the parenthesis string is valid by `push_front(c)`, otherwise reset p=0.
3. Convert deque `q` to string and return

Let's see the process for the testcase `"lee(t(c))o)de))())("` which is adding some outputs for submitted code
```
1st transverse:
l : p= 0 t= l
e : p= 0 t= le
e : p= 0 t= lee
( : p= 1 t= lee(
t : p= 1 t= lee(t
( : p= 2 t= lee(t(
c : p= 2 t= lee(t(c
) : p= 1 t= lee(t(c)
) : p= 0 t= lee(t(c))
o : p= 0 t= lee(t(c))o
) : removing
d : p= 0 t= lee(t(c))od
e : p= 0 t= lee(t(c))ode
) : removing
) : removing
( : p= 1 t= lee(t(c))ode(
) : p= 0 t= lee(t(c))ode()
) : removing
( : p= 1 t= lee(t(c))ode()(
---
t= lee(t(c))ode()(
transverse reversely:
( : removing
) : p= -1 q= )
( : p= 0 q= ()
e : p= 0 q= e()
d : p= 0 q= de()
o : p= 0 q= ode()
) : p= -1 q= )ode()
) : p= -2 q= ))ode()
c : p= -2 q= c))ode()
( : p= -1 q= (c))ode()
t : p= -1 q= t(c))ode()
( : p= 0 q= (t(c))ode()
e : p= 0 q= e(t(c))ode()
e : p= 0 q= ee(t(c))ode()
l : p= 0 q= lee(t(c))ode()
```

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n)\to O(1)$$
# Code||C++ 14ms Beats 95.19%
```C++ []
#pragma GCC optimize("O3", "unroll-loops")
class Solution {
public:
    string minRemoveToMakeValid(string& s) {
        string t;//Temporary string to store valid parentheses
        int p=0;// p is the balance of '(' and ')'

        // Forward pass to remove excess ')' and ensure balance
        for(char c: s){
            p+=(c=='(')-(c==')');//find the depth for c
            if (p>=0) t.push_back(c);// depth>=0, valid
            else p=0;// ')' too many, reset p
        }
        p=0;// Reset balance for backward pass
        deque<char> q;// Using deque for efficient push_front

        //Backward pass to remove excess '('
        for(int i=t.size()-1; i>=0; i--){
            char c=t[i];
            p+=(c=='(')-(c==')');//find the depth for c 
            if (p<=0)q.push_front(c); // depth<=0, valid
            else p=0; // '(' too many, reset p
        }

        //Convert deque to string and return
        return string(q.begin(), q.end());
    }
};


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

```python []
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        t=[]
        p=0
        for c in s:
           p+=(c=='(')-(c==')')
           if p>=0: t.append(c)
           else: p=0
        p=0
        q=deque() 
        for c in t[::-1]:
            p+=(c=='(')-(c==')')
            if p<=0: q.appendleft(c)
            else: p=0
        return ''.join(q)
```
# 2nd C++ using string & reverse||C++ 14ms Beats 95.19%

Almost the same as the 1st one. Just use reverse & reuse `s` to replace the role played by deque `q`.
```
#pragma GCC optimize("O3", "unroll-loops")
class Solution {
public:
    string minRemoveToMakeValid(string& s) {
        string t;
        int p=0, n=s.size();
        for(char c: s){
            p+=(c=='(')-(c==')');
            if (p>=0) t.push_back(c);
            else p=0;
        }
        p=0;
        s="";
        for(int i=t.size()-1; i>=0; i--){
            char c=t[i];
            p+=(c=='(')-(c==')');
            if (p<=0)  s.push_back(c);
            else p=0;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};

```
# Codes using only string with SC O(1)||C: 2ms Beats 98.08% C++:6ms Beats 99.97%

__Less containers less elapsed time!__
Thanks to suggestions by @Sergei. Try to construct a 2 pass solution.
Resue string `s`, it doesn't need other containers. 1st backward transverse marks excess '('s with '@'.
The 2nd forward transverse obtains the valid parentheses string. C++ is really a 2 pass solution. The coresponding C code uses strlen function, & hence a 3 pass solution.
```C++ []
#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;
        }
    //    cout<<s<<endl;
        int sz=n;
        p=0;
        for(int i=0, j=0; i<n; i++){
            char c=s[i];
            p+=(c=='(')-(c==')');
            if (c!='@' && p>=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';
}();
```
```C []
#pragma GCC optimize("O3", "unroll-loops")
char* minRemoveToMakeValid(char* s) {
    int p=0, n=strlen(s);
    for(register int i=n-1; i>=0; i--){
        char c=s[i];
        p+=(c=='(')-(c==')');
        if (p>0) s[i]='@', p=0;
    }
    int sz=n;
    p=0;
    for(register int i=0, j=0; i<n; i++){
        char c=s[i];
        p+=(c=='(')-(c==')');
        if (c!='@' && p>=0) s[j++]=c;
        else sz--, p=0;
    }
    s[sz]='\0';
    return s;
}
```





['String', 'Queue', 'C', 'C++', 'Python3']