<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:
    vector<string>ans;

    void call(string s, int pos, string output , int open , int close)
    {
        if(pos==s.size())
        {
            if(open!=close || output.size()==0) //output.size()==0 not needed if we use set
                return;
            if(ans.size()>0  && ans.back().size()>output.size())
                return;
            if(ans.size()>0 && ans.back().size()<output.size())
            {
                ans.clear();
            }
            ans.push_back(output);
            return;
        }

        if(s[pos]=='(')
        {
            int j=pos;
            while(j<s.size()&&s[j]=='(')
                j++;
            call(s,j,output,open,close);
            call(s,pos+1,output+'(',open+1,close);
        }
        else if(s[pos]==')')
        {
            int j=pos;
            while(j<s.size()&&s[j]==')')
                j++;
            call(s,j,output,open,close);
            if(open>close)
                call(s,pos+1,output+')',open,close+1);
        }
        else
            call(s,pos+1,output+s[pos],open,close);
    }
    vector<string> removeInvalidParentheses(string s) {
        ans.clear();
        ans.push_back("");
        call(s,0,"", 0,0);
        // set<string>ss(ans.begin(),ans.end());
        // return vector<string>(ss.begin(),ss.end());
        return ans;
    }
};
145006