• ㊗️
• 大家
• offer
• 多多！

## Problem

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

Return a list of unique strings that are valid with the minimum number of removals. 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.

## Code

class Solution {
List<String> res;

public List<String> removeInvalidParentheses(String s) {
res = new ArrayList<>();
removeHelper(s, 0, 0, '(', ')');
return res;
}

public void removeHelper(String s, int iStart, int jStart, char left, char right) {
int leftCount = 0, rightCount = 0;

for (int i = iStart; i < s.length(); i++) {
if (s.charAt(i) == left)
leftCount++;
if (s.charAt(i) == right)
rightCount++;

// extra right, need to remove
if (rightCount > leftCount) {
// 在i之前找到 ) 并且remove
for (int j = jStart; j <= i; j++) {
// skip duplicates 只remove每组 ) 中的第一个
if (s.charAt(j) == right && (j == jStart || s.charAt(j - 1) != right)) {
String curr = s.substring(0, j) + s.substring(j + 1, s.length());
removeHelper(curr, i, j, left, right);
}
}

return;
}
}

// valid right parenthesis detected
// now check opposite direction
String reversed = new StringBuilder(s).reverse().toString();
if (left == '(') {
removeHelper(reversed, 0, 0, ')', '(');
} else {
}
}
}