<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 {
private:

    unordered_map <int, unordered_set <string> > result;
    int minCount = INT_MAX;
    bool isValid(string &input)
    {
        int open = 0;
        for(int i = 0; i < input.size(); i++)
        {
            if(input[i] == '(')
                open++;
            else if(input[i] == ')')
                open--;
            
            if(open < 0)
                return false;
        }
        return (open == 0);
    }

    void removeInvalid(int index, const string &input, string curString, int count)
    {
        while(index < input.size() && input[index] != ')' && input[index] != '(')
        {
            curString += input[index];
            index++;
        }

        if(index >= input.size())
        {
            if(isValid(curString))
            {
                // cout << count << " : " << curString << endl;
                minCount = min(minCount, count);
                result[count].insert(curString);    
            }
            return;
        }

        removeInvalid(index+1, input, curString + input[index], count);
        removeInvalid(index+1, input, curString, count+1);
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        
        removeInvalid(0, s, "", 0);
        vector <string> output;
        for(auto val : result[minCount])
            output.push_back(val);
        return output;
    }
};
251626