# LeetCode 301. Remove Invalid Parentheses

## Description

https://leetcode.com/problems/remove-invalid-parentheses/

Given a string `s` that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

```Input: s = "()())()"
Output: ["(())()","()()()"]
```

Example 2:

```Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
```

Example 3:

```Input: s = ")("
Output: [""]
```

Constraints:

• `1 <= s.length <= 25`
• `s` consists of lowercase English letters and parentheses `'('` and `')'`.
• There will be at most `20` parentheses in `s`.

## Explanation

Use depth-first search to find valid strings.

## Python Solution

``````class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
results = []

left, right = self.left_right_count(s)

self.dfs_helper(s, left, right, 0, results)

return results

def left_right_count(self, s):
left = 0
right = 0

for c in s:
if c == '(':
left += 1
elif c == ')':
if left > 0:
left -= 1
else:
right += 1

return left, right

def is_valid(self, s):
left, right = self.left_right_count(s)
return left == 0 and right == 0

def dfs_helper(self, s, left, right, start, results):
if left == 0 and right == 0:
if self.is_valid(s):
results.append(s)
return

for i in range(start, len(s)):
if i > start and s[i] == s[i - 1]:
continue

if s[i] == '(':
self.dfs_helper(s[:i] + s[i + 1:], left - 1, right, i, results)
elif s[i] == ')':
self.dfs_helper(s[:i] + s[i + 1:], left, right - 1, i, results)
``````
• Time Complexity: O(N).
• Space Complexity: O(N).