<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 getMinimumRemovals(string &str){

        stack<char> s;

        for(int i=0;i<str.size();i++){
            if(str[i]=='('){
                s.push(str[i]);
            }
            else if(str[i]==')'){
                if(s.empty() || (!s.empty() && s.top()==')')){
                    s.push(')');
                }
                else{
                    s.pop();
                }
            }
        }

        return s.size();

    }

    void solve(string str,vector<string> &ans,int brackets,unordered_set<string> &st){

        if(st.find(str)!=st.end()){
            return;
        }
        st.insert(str);
        if(brackets==0 && getMinimumRemovals(str)==0){
            ans.push_back(str);
            return;
        }
        
        for(int i=0;i<str.size();i++){
            string left=str.substr(0,i);
            string right=str.substr(i+1,str.size()-i);
            solve(left+right,ans,brackets-1,st);
        }

    }

    vector<string> removeInvalidParentheses(string str) {

        vector<string> ans;
        string temp;
        unordered_set<string> st;
        int minBracketsToRemove=getMinimumRemovals(str);
        solve(str,ans,minBracketsToRemove,st);

        return ans;
        
    }
};
91696