301. Remove Invalid Parentheses (Hard)

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

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses `(` and `)`.

Example 1:

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

Example 2:

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

Example 3:

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

Solutions

``````class Solution {

// This is a brute force solution.

// the minimum delete operations. Any outcome patterns the requires more than this is invalid.
int minDelete = Integer.MAX_VALUE;

public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();

if (s == null || s.length() == 0) {

return ans;
}

minDelete = calculateMinDelete2(s);

System.out.println(minDelete);

recurse(s.toCharArray(), 0, "", ans, 0, 0, 0);

if (ans.size() == 0) {
}

return ans;
}

private int calculateMinDelete(String s) {
int invalidP = 0;

int openP = 0;
int closeP = 0;

for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
openP++;
}

if (s.charAt(i) == ')') {
closeP++;
}

if (openP < closeP) {
openP = 0;
closeP = 0;
invalidP++;
}
}

// do not forget the situation the the last char is open parenthese, say "(()("
if (openP > closeP) {
// be careful, not invalidP++;
invalidP += openP - closeP;
}

return invalidP;
}

private int calculateMinDelete2(String s) {
int invalidClose = 0;

Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {

continue;
}

if (s.charAt(i) == ')') {
if (stack.isEmpty()) {
invalidClose++;
} else {
stack.pop();
}
}
}

return invalidClose + stack.size();
}

private void recurse(char[] str, int start, String result, List<String> ans, int openP, int closeP, int delete) {
if (delete > minDelete) {
return;
}

// reach the end of the string
if (start == str.length) {

// invalid parentheses
if (openP != closeP) {
return;
}

if (ans.contains(result)) {
return;
}

return;
}

// Open parentheses can never be less than close parentheses. Otherwise it is invalid parentheses string.
if (openP < closeP) {
return;
}

if (str[start] == '(') {
recurse(str, start + 1, result + "(", ans, openP + 1, closeP, delete);

recurse(str, start + 1, result, ans, openP, closeP, delete + 1);

return;
}

if (str[start] == ')') {
recurse(str, start + 1, result + ")", ans, openP, closeP + 1, delete);

recurse(str, start + 1, result, ans, openP, closeP, delete + 1);

return;
}

recurse(str, start + 1, result + str[start], ans, openP, closeP, delete);
}
}
``````