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.