Reference: LeetCode
Difficulty: Hard

My Post: Java Solution with Detailed Comments (easy-understand, readable)

Problem

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Input: "()())()"
Output: ["()()()", "(())()"]

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

Input: ")"
Output: [""]

Input: ")a"
Output: ["a"]

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

Input: "v)k)()"
Output: ["vk()"]

Input: "())))()v(k"
Output: ["()()vk"]

// There are many test cases... If you write a good function of delete count calculation, you don't have to worry about those corner and special cases!

Follow up: Pruning

Analysis

Backtracking

Main function:

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();

// calculate the number of "(" and ")" we should delete
int[] count = getDeleteCount(s);
int leftCount = count[0];
int rightCount = count[1];

StringBuilder sb = new StringBuilder();
backtrack(leftCount, rightCount, 0, 0, 0, sb, s, result, false, false);

return result;
}

The getDeleteCount function helps determine how many ( and ) we will delete.

Note:

  • This function is very important. ( should be calculated starting from the right side of the array, which is opposed to the way we did for (.
  • If this function does not provide correct number of ( we should delete, you have to handle a lot of corner and special cases.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Return how many "(" and ")" should we delete.
private int[] getDeleteCount(String s) {
int L1 = 0, R1 = 0;
int L2 = 0, R2 = 0;
int leftCount = 0, rightCount = 0;
for (int i = 0; i < s.length(); ++i) {
char ch1 = s.charAt(i); // from left
char ch2 = s.charAt(s.length() - i - 1); // from right
if (ch1 == '(') L1 += 1; // remember to skip other letters
if (ch1 == ')') R1 += 1;
if (ch2 == '(') L2 += 1;
if (ch2 == ')') R2 += 1;
rightCount = Math.max(rightCount, R1 - L1);
leftCount = Math.max(leftCount, L2 - R2);
}
return new int[] { leftCount, rightCount };
}

Backtracking function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* leftCount: # of "(" we should delete
* rightCount: # of ")" we should delete
* L: # of "(" we have selected
* R: # of ")" we have selected
* pos: current index in the string
* deletedLeft: indicate whether we deleted "(" in the previous level
* deletedRight: indicate whether we deleted ")" in the previous level
* (deletedLeft and deletedRight are for duplicate checking)
*
* It means that if you have deleted "(" at the previous level,
* you should not choose "(" at the current level because it incurs duplicate results.
*/
private void backtrack(int leftCount, int rightCount, int L, int R, int pos,
StringBuilder sb, String s, List<String> result,
boolean deletedLeft, boolean deletedRight) {
// base case
if (L < R) { // L < R (not balanced)
return;
}
if (pos == s.length()) { // time to add the result
if (leftCount == 0 && rightCount == 0 && L == R) { // check if it is a valid string
result.add(sb.toString());
}
return;
}

char ch = s.charAt(pos);
if (ch == '(') {
// select
if (deletedLeft == false || s.charAt(pos - 1) != '(') { // check for duplicates
sb.append(ch);
backtrack(leftCount, rightCount, L + 1, R, pos + 1, sb, s, result, false, false);
sb.deleteCharAt(sb.length() - 1);
}
// do not select it (delete)
if (leftCount > 0) {
backtrack(leftCount - 1, rightCount, L, R, pos + 1, sb, s, result, true, false);
}
}
else if (ch == ')') {
// select
if (deletedRight == false || s.charAt(pos - 1) != ')') { // check for duplicates
sb.append(ch);
backtrack(leftCount, rightCount, L, R + 1, pos + 1, sb, s, result, false, false);
sb.deleteCharAt(sb.length() - 1);
}
// do not select it (delete)
if (rightCount > 0) {
backtrack(leftCount, rightCount - 1, L, R, pos + 1, sb, s, result, false, true);
}
}
else { // other letter
sb.append(ch);
backtrack(leftCount, rightCount, L, R, pos + 1, sb, s, result, false, false);
sb.deleteCharAt(sb.length() - 1);
return;
}
}

Time: $O(2^N)$ is the upper bound, but we have pruning.
Space: $O(N)$ because of call stacks.


Comment