<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:
    unordered_set<string> unique_list;
    int global_min = INT_MAX;
    void rec(string& s ,string curr,  int index, int left_count, int right_count , int left_rem, int right_rem){
        
        //if(right_count > left_count) return;
        if(index== s.size()){
            if(left_rem ==0 && right_rem ==0 ){ 
                unique_list.insert(curr);
            }
        }else{
            //if no bracket continue;
            if(s[index] != '(' && s[index] != ')' ){
               
                rec(s, curr+s[index] , index+1, left_count, right_count ,left_rem,right_rem);
            }else{
                //remove || dont consider the bracket 
                if( (s[index] == '(' && left_rem >0 ) || (s[index] == ')' && right_rem>0 ) ){
                    rec(s, curr , 
                        index+1, 
                        left_count, 
                        right_count, 
                        left_rem - (s[index] == '(' ?  1 : 0 ),
                        s[index] == ')' ? right_rem - 1 : right_rem
                        );
                }
                // don't remove the bracket
                if(s[index] == '('){
                    rec(s, curr+s[index] , index+1, left_count+1, right_count , left_rem,right_rem);
                    
                }else if(right_count < left_count){
                    rec(s, curr+s[index] , index+1, left_count, right_count+1 , left_rem,right_rem);
                }
            }
        }
    }
    vector<string> removeInvalidParentheses(string s) {
        int left_rem =0;
        int right_rem =0;
        for(int i=0; i< s.size() ; i++){
            if(s[i] == '('){
                left_rem++;
            }else if(s[i] == ')'){
                right_rem = left_rem > 0 ? right_rem : right_rem+1;
                left_rem = left_rem > 0 ? left_rem - 1 : left_rem;
            }
        }
        
        rec(s,"",0,0,0, left_rem, right_rem);
        vector<string> out;


        for(string tmp : unique_list){
            out.emplace_back(tmp);
        }
        return out;
    }
};
504849