<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 (k < 0 or open > n or close > open) return;
        if (idx==s.length()){
            // if (k==0 and minDeletionsToBalanceString(tans) == 0){ // balanced string
            //     ans.insert(tans);
            // }
            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