Remove Invalid Parentheses

About the problem:

Here we are given a string, str, consisting of letters and parentheses only. We are to get rid of the minimum number of invalid parentheses from the input and return all the possible valid strings.

Example 1:
Input: str = “()((a)(©)”
Output: [ “()(a)(©)” , “()((a)c)” ]

Example 2:
Input: str = “)))((((a)”
Output: [ “(a)” ]

Approach #1: BFS

We can see that this problem involves recurrences, thus algorithms like BFS work fine. We will traverse through a string and delete one parenthesis at a time and check if any string on the current level is valid or not.
At the topmost, the string is original with zero deletions. At each level the number of deletions increases and we stop deleting from the string when the string is valid. Here we also use an explicit map to not repeat for the same string.

Algorithm:

1. Check if the input string is already balanced. If yes, return a vector with the input string.

2. Now declare an explicit map of <string,bool> mp1,mp2 to store traversed value.

3. Insert input string in mp1 and traverse until mp1 is not empty.

4. a. Iterative over mp1.

5. b. For each string in mp1 delete one character at a time and insert it in mp2.

6. c. Now check if the string is valid and is not present in mp2, push it in the result vector.

7. d. If any string is valid in this array we break the loop and return the result vector.

8. Swap the maps and clear mp2.

9. Return the res vector at the end.

Code:

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
bool check(string s, int k) {
  int c = 0;
  for (int i = 0; i < s.size(); i++) {
    if (i != k && s[i] == '(') {
      c += 1;
    }
    if (i != k && s[i] == ')') {
      c -= 1;
      if (c < 0) {
        return false;
      }
    }
  }
  return c == 0;
}

vector < string > removeInvalidParentheses(string s) {
  vector < string > res;
  unordered_map < string, bool > mp1;
  unordered_map < string, bool > mp2;

  if (check(s, -1)) {
    res.push_back(s);
    return res;
  }

  mp1[s] = true;

  while (!mp1.empty()) {
    bool check_flag = false;
    for (auto it1 = mp1.begin(); it1 != mp1.end(); it1++) {
      string tmp = it1 - > first;
      for (int i = 0; i < tmp.size(); i++) {
        string tmp2 = tmp;
        tmp2.erase(i, 1);
        if (check(tmp, i) && mp2.find(tmp2) == mp2.end()) {
          res.push_back(tmp2);
          check_flag = true;
        }
        mp2[tmp2] = true;
      }
    }
    if (check_flag) {
      return res;
    } else {
      mp1 = mp2;
      mp2.clear();
    }
  }

  return res;
}

Approach #2: Backtracking

Algorithm:

Count the number of misplaced left and right brackets in variables left and right respectively. Our target is to delete exactly left left opening brackets and right right closing brackets.
We traverse the given string s and if the s[i] is an opening bracket (, then we discard it if the number of left brackets discarded yet to get to this point is less than left. Also, we try the other path of including this bracket. In case we come across a ), we either discard it if the number of right brackets discarded so far is less than right, or we include it if the bracCount variable does not go negative. (The brackCount variable is incremented if we encounter a ( and is decremented if we encounter a )).
If s[i] is not a bracket, we simply add it to the string.
If in the end, the bracCount variable is 0, then we include the string so formed in our list of valid strings, otherwise not.
In order to avoid the same string being included multiple times, after not including a bracket (either ( or )), we skip over to the minimum index to the right of i where this bracket does not occur. It is easy to see that once we discard a bracket at some index, performing the same logic with the same kind of bracket at the next index will result in duplicate strings. If in the process of skipping brackets, we run out of the number of brackets we can discard (left or right), we do not go any further.

Code:

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
60
61
62
63
64
void recur(string & s, int i, int bracCount, int left, int right,
  string str, vector < string > & res) {
  if (i == s.length()) {
    if (bracCount == 0) {
      res.push_back(str);
    }
    return;
  }

  if (s[i] == '(') {
    recur(s, i + 1, bracCount + 1, left, right, str + '(', res);
    if (left > 0) {
      while (i < s.length() && s[i] == '(' && left > 0) {
        i++;
        left--;
      }

      if (s[i] != '(') {
        recur(s, i, bracCount, left, right, str, res);
      }
    }
  } else if (s[i] == ')') {
    if (bracCount - 1 >= 0) {
      recur(s, i + 1, bracCount - 1, left, right, str + ')', res);
    }

    if (right > 0) {
      while (i < s.length() && s[i] == ')' && right > 0) {
        i++;
        right--;
      }

      if (s[i] != ')') {
        recur(s, i, bracCount, left, right, str, res);
      }
    }
  } else {
    recur(s, i + 1, bracCount, left, right, str + s[i], res);
  }
}

vector < string > removeInvalidParentheses(string s) {
  vector < string > res;
  int maxLen = 0;
  int left = 0, right = 0;

  for (int i = 0; i < s.length(); i++) {
    if (s[i] == '(') {
      left++;
    } else if (s[i] == ')') {
      if (left == 0) {
        right++;
      } else {
        left--;
      }
    }
  }
  if (left + right == s.length()) {
    res.push_back("");
    return res;
  }
  recur(s, 0, 0, left, right, "", res);
  return res;
}

Time Complexity

O(2^N). Every character could be a parenthesis, requiring us to explore both choices (including it in the result, or not).

Space Complexity

O(2^N). Every choice to include or not include a character could result in a valid string.