<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>

from functools import lru_cache

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        @lru_cache(None)
        def _remove(cur="", pos=0, state=0):
            if pos == len(s):
                if state == 0 and len(cur) == max_len:
                    return {''.join(cur)}
                else:
                    return set()
            
            if (len(cur) + (len(s) - pos) < max_len) or (state > right[pos]):
                return set()

            if s[pos] not in ['(', ')']:
                return _remove(cur + s[pos], pos + 1, state)
            
            result = set()
            if s[pos] == '(':
                result = _remove(cur + s[pos], pos + 1, state + 1)
            elif state > 0:
                result = _remove(cur + s[pos], pos + 1, state - 1)
            
            result |= _remove(cur, pos + 1, state)
            return result
        
        balance = 0
        remove = 0
        for l in s:
            if l == '(':
                balance += 1
            elif l == ')':
                if balance:
                    balance -= 1
                else:
                    remove += 1
        remove += balance
        max_len = len(s) - remove

        right = [0] * (len(s) + 1)
        for i in range(len(s) - 1, -1, -1):
            right[i] = right[i + 1] + (s[i] == ')')

        return list(_remove())
17900