<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:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def is_valid(string):
            opens = 0
            for char in string:
                if char == '(': opens += 1
                elif char == ')':
                    opens -= 1
                    if opens < 0: return False
            return opens == 0

        if not s: return []
        res = set()
        visited = set()
        visited.add(s)
        found = False

        q = deque([[s]])
        while q:
            curr_layer = q.popleft()
            next_layer = []
            for string in curr_layer:
                if is_valid(string):
                    res.add(string)
                    found = True
                
                for i in range(len(string)):
                    if string[i] == '(' or string[i] == ')':
                        new_string = string[:i]+string[i+1:]
                        if new_string not in visited:
                            next_layer.append(new_string)
                            visited.add(new_string)
            if found:
                break
            if next_layer: q.append(next_layer)

        return list(res)

    def removeInvalidParentheses2(self, s: str) -> List[str]:
        def isValid(s):
            opens = 0
            for char in s:
                if char == '(': opens += 1
                elif char == ')':
                    opens -= 1
                    if opens < 0: return False
            return not opens
        
        q = deque([s])
        visited = set()
        visited.add(s)
        min_removal_found = False
        res = []
        while q:
            curr = q.popleft()
            if isValid(curr):
                res.append(curr)
                min_removal_found = True

            if not min_removal_found:
                for i in range(len(curr)):
                    if curr[i] == '(' or curr[i] == ')':
                        new_str = curr[:i] + curr[i+1:]
                        if new_str not in visited:
                            q.append(new_str)
                            visited.add(new_str)
        return res

    def removeInvalidParenthesesTLE(self, s: str) -> List[str]:
        def numInvalidParens(s):
            opens, close = 0,0
            for char in s:
                if char == '(':
                    opens += 1
                elif char == ')':
                    if opens: opens -= 1
                    else: close += 1
            return opens+close

        def helper(string, removal_count, invalid_parens, res):
            if removal_count == invalid_parens and numInvalidParens(string) == 0:
                res.add(string)
                return
            
            for i in range(len(string)):
                if string[i] == '(' or string[i] == ')':
                    new_str = string[:i] + string[i+1:]
                    helper(new_str, removal_count+1, invalid_parens, res)
        
        invalid_parens = numInvalidParens(s)
        if invalid_parens == 0: return [s]

        res = set()
        helper(s, 0, invalid_parens, res)
        return list(res)
            
        
17700