<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:
    set<string> ret;
    set<int> cur_idx_remove;

    vector<int> suffix_left; // number of ( in s[i...]
    vector<int> suffix_right; // number of ( in s[i...]

    string remove_idx(string s, set<int> idx_remove) {
        string ret;
        for(int i=0;i<s.length();i++) {
            if(idx_remove.find(i) == idx_remove.end())
                ret.push_back(s[i]);
        }
        return ret;
    }

    bool is_valid(string s) {
        int cnt_left = 0;
        for(char c : s) {
            if(c == '(')    cnt_left++;
            else if(c == ')') {
                if(cnt_left == 0)   return false;
                cnt_left--;
            }
        }
        return (cnt_left == 0);
    }

    void backtrack(string& s, int cur_idx, int left_remove, int right_remove) {
        if(left_remove == 0 && right_remove == 0) {
            string cur = remove_idx(s,cur_idx_remove);
            if(is_valid(cur))
                ret.insert(cur);
            return;
        }
        if(left_remove < 0 || right_remove < 0 || cur_idx >= s.length() || left_remove > suffix_left[cur_idx] || right_remove > suffix_right[cur_idx])    return;
        
        backtrack(s,cur_idx+1,left_remove,right_remove);
        if(s[cur_idx] == '(') {
            cur_idx_remove.insert(cur_idx);
            backtrack(s,cur_idx+1,left_remove-1,right_remove);
            cur_idx_remove.erase(cur_idx);
        }
        if(s[cur_idx] == ')') {
            cur_idx_remove.insert(cur_idx);
            backtrack(s,cur_idx+1,left_remove,right_remove-1);
            cur_idx_remove.erase(cur_idx);
        }
    }

    vector<string> removeInvalidParentheses(string s) {
        suffix_left.resize(s.length()+1);
        suffix_right.resize(s.length()+1);

        suffix_left[s.length()] = suffix_right[s.length()] = 0;
        for(int i=s.length()-1;i>=0;i--) {
            suffix_left[i] = suffix_left[i+1] + (s[i] == '(');
        }

        for(int i=s.length()-1;i>=0;i--) {
            suffix_right[i] = suffix_right[i+1] + (s[i] == ')');
        }


        int left_remove = 0;
        int right_remove = 0;

        int cnt_left = 0;
        for(char c:s) {
            if(c == '(')    cnt_left++;
            else if(c == ')') {
                if(cnt_left == 0)   right_remove++;
                else    cnt_left--;
            }
        }
        left_remove = cnt_left;

        backtrack(s,0,left_remove,right_remove);

        vector<string> ans;

        for(auto it = ret.begin();it!=ret.end();it++) {
            ans.push_back(*it);
        }
        return ans;
    }
};
444875