301. Remove Invalid Parentheses

The idea behind is scan the entire string first and compute the invalid parenthesis. We need two counters for left invalid parenthesis and right invalid parenthesis respectively and the computation is very easy such that increase the left whenever ‘(’ appears and decrease the left if left is not 0 otherwise increase the right.
After the preprocessing above, we do dfs per character throughout the string. For each character, if it is neither ‘(‘ nor ‘)’, we add this character to solution and continue scanning next character. If it is ‘(‘ and if left is larger than 0, we have one more choice, i.e. we can skip this left parenthesis, and dfs next character. When skipping, we reduce left by 1. On other hand, no matter left is larger than 0 or not, we can keep this left parenthesis in solution anyway, and move to next character. Same logic to right parenthesis. However, for right parenthesis, we need to keep track if it is valid to place a ‘)’ in the solution. So we added a pair to indicate how many left parentheses have been placed before and we only allocate the right parenthesis when pair is not 0.
For the termination of dfs, we check if it is the end character and if left, right and pair is 0. If so, the solution is a valid one and we push it to the result. Note, to avoid duplication (e.g. ()), it’s be same to remove first ‘)’ or the second ‘)’), we use unordered_set to keep the result.

1:  class Solution {  
2:  public:  
3:    vector<string> removeInvalidParentheses(string s) {  
4:      int left = 0, right = 0;  
5:      unordered_set<string> res;  
6:      for (char c : s) {  
7:        if (c == '(') left++;  
8:        else if (c == ')') {  
9:          if (left) left--;  
10:          else right++;  
11:        }  
12:      }  
13:      dfs(s, 0, 0, left, right, "", res);  
14:      return vector<string>(res.begin(), res.end());  
15:    }  
16:    void dfs(string &s, int index, int pair, int left, int right, string sol, unordered_set<string> &res) {  
17:      if (index == s.size()) {  
18:        if (left == 0 && right == 0 && pair == 0) res.insert(sol);  
19:        return;  
20:      }  
21:      if (s[index] == '(') {  
22:        if (left > 0) dfs(s, index+1, pair, left-1, right, sol, res);  
23:        dfs(s, index+1, pair+1, left, right, sol+s[index], res);  
24:      } else if (s[index] == ')') {  
25:        if (right > 0) dfs(s, index+1, pair, left, right-1, sol, res);  
26:        if (pair > 0) dfs(s, index+1, pair-1, left, right, sol+s[index], res);  
27:      } else {  
28:        dfs(s, index+1, pair, left, right, sol+s[index], res);  
29:      }  
30:    }  
31:  };  

The top rated solution plays a trick. It only focus on solving subproblem that ')' doesn't match. Would we detect a ')', we will try to remove every ')' before inclusively and call itself to fix the remaining string. So it is a DFS. In order to avoid duplicates like "())" which generates "()" twice, we'll remove the last ')' in a consecutive sequence. Also we need to keep track of last ')' before recursively calling itself to avoid duplicates. Note if we start from 0 again, we'll duplicate the work the last work in the recursive stack. So far we are done with mismatch on ')', then the question will be how about mismatch on '(', for example, "(()"? The trick is to reverse the string and do the same algorithm again!

1:  class Solution {  
2:  public:  
3:    vector<string> removeInvalidParentheses(string s) {  
4:      vector<string> res;  
5:      helper(s, 0, 0, "()", res);  
6:      return res;  
7:    }  
8:    void helper(string s, int start, int last, string p, vector<string> &res) {  
9:      for (int stack = 0, i = start; i < s.size(); i++) {  
10:        if (s[i] == p[0]) stack++;  
11:        else if (s[i] == p[1]) stack--;  
12:        if (stack >= 0) continue;  
13:        for (int j = last; j <= i; j++) {  
14:          if (s[j] == p[1] && (j == last || s[j-1] != p[1])) {  
15:            helper(s.substr(0, j)+s.substr(j+1), i, j, p, res);  
16:          }  
17:        }  
18:        return;  
19:      }  
20:      reverse(s.begin(), s.end());  
21:      if (p[0] == '(') helper(s, 0, 0, ")(", res);  
22:      else res.push_back(s);  
23:    }  
24:  };