<p>Given a string <code>s</code> that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.</p>

<p>Return <em>a list of <strong>unique strings</strong> that are valid with the minimum number of removals</em>. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;()())()&quot;
<strong>Output:</strong> [&quot;(())()&quot;,&quot;()()()&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(a)())()&quot;
<strong>Output:</strong> [&quot;(a())()&quot;,&quot;(a)()()&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;)(&quot;
<strong>Output:</strong> [&quot;&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 25</code></li>
	<li><code>s</code> consists of lowercase English letters and parentheses <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code>.</li>
	<li>There will be at most <code>20</code> parentheses in <code>s</code>.</li>
</ul>

// class Solution {
// public:
//     int minDeletionsToBalanceString(string s){
//         stack<char> st;
//         for(auto c: s){
//             if (c!='(' and c!=')') continue; // s can contain lowercase characters as well
//             if(c=='(')
//                 st.push('(');
//             else{
//                 if(st.empty() or st.top()==')') st.push(c); // Push in 2 cases: when st is empty and st.top() is cloing bracket
//                 else st.pop();
//             }
//         }
//         // number of remaining brackets indicate minimum deletions to make string balanced
//         return st.size();
//     }

//     void solve(string s, int k, int idx, string tans, set<string>& ans, int open, int close, int n){
//         // cout<<tans<<endl;
//         if (idx==s.length()){
//             if (k==0 and minDeletionsToBalanceString(tans) == 0){ // balanced string
//                 ans.insert(tans);
//             }
//             return;
//         }
        
//         if (s[idx]!='(' and s[idx]!=')'){ // lowercase only 1 option to pick
//             solve(s, k, idx+1, tans+s[idx], ans, open, close, n);
//         }
//         else if (s[idx]=='('){ // 2 options for the opening bracket - pick and not pick 
//             if (open < n) // pick only when open < n
//                 solve(s, k, idx+1, tans+s[idx], ans, open+1, close, n);
//             // not pick
//             solve(s, k-1, idx+1, tans, ans, open, close, n);
//         }
//         else if(s[idx]==')'){ // 2 options for the closing bracket - pick and not pick 
//             if (close < open) // pick this closing bracket only when close < open
//                 solve(s, k, idx+1, tans+s[idx], ans, open, close+1, n);
//             // not pick
//             solve(s, k-1, idx+1, tans, ans, open, close, n);
//         }

//     }
//     vector<string> removeInvalidParentheses(string s) {
//         int k = minDeletionsToBalanceString(s);
//         cout<<"k "<<k<<endl;
//         int count= 0;
//         for(auto c: s){
//             if (c=='(' or c==')') count+=1;
//         }
//         int n = (count - k)/2; // count contains only the opening and closing brackets, cannot consider s.length() as string also contains lowercase letters
        
//         set<string> ans;

//         solve(s, k, 0, "", ans, 0, 0, n);

//         vector<string> res;
//         for (auto s: ans) res.push_back(s);
        
//         return res;
//     }
// };

// // Solution contains of 2 steps:
// // First find the minimum number of deletions that needs to be done to make the string balanced. A balanced string requires 0 deletions
// // Apply backtracking based solution where you deletes that many min brackets and check in the base case if the string is balanced
//     // The recursion steps(else part) can be optimised, some kind of pruning is required to minimise the number of recursion calls.




class Solution {
public:
     int getMin(string s){
      stack<char> st;
      for (int i=0;i<s.length();i++){
          if (s[i] == '('){
              st.push(s[i]);
          }
          else if(s[i] == ')'){
              if(st.empty()){
                  st.push(s[i]);
              }
              else if(st.top() == ')'){
                  st.push(s[i]);
              }
              else{
                  st.pop();
              }
          }
      }
        
        return st.size();  
    }
    
    void solve(string s, int i, int open, int close, string ans, vector<string>& res, int mr, int n){
        // cout<<open<<" "<<close<<endl;
        
        if(mr<0 || open>n || close>open) return;
        if(i>=s.length()){
            // cout<<ans<<endl;
            if(find(res.begin(),res.end(),ans)==res.end()){
                res.push_back(ans);
            }
            return;
        }
        
        
        if(s[i]=='('){
            solve(s,i+1,open+1,close,ans+"(",res,mr,n);
            solve(s,i+1,open,close,ans,res,mr-1,n);
        }
        else if(s[i]==')'){
            solve(s,i+1,open,close+1,ans+")",res,mr,n);
            solve(s,i+1,open,close,ans,res,mr-1,n);
        }
        else{
            solve(s,i+1,open,close,ans+s[i],res,mr,n);
        }
    }
    vector<string> removeInvalidParentheses(string s) {
        int mr=getMin(s);
        int c=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='(' || s[i]==')') c++;
        }
        int n = (c-mr)/2;
        vector<string> res;
        solve(s,0,0,0,"",res,mr,n);
        return res;
    }
};
111688