301. Remove Invalid Parentheses

use unmatched count to find the final ans

if unmatched count == 0 means can be add to result (and i == s.size()...currStr == maxLen

### 去重方法

第一個字是 B (ret.back()),  之後要加的 Ａ是相同的字符(S[i), 中間 * 是其他字

如果要娶兩個Ａ, 怎麼取會是 unique的
   A    *  A   * A * A    s[i]

B                            ret

B ≠ A (ret.back() ≠ S[0]) ⇒ 可以 不選 A (x), 也可選 A   ,   跟  2^n 想法一樣

```java
if ret.back() != s[i] 
    ret + s[i]  // 選 A (s[i]), ret.back() 是B
    ret // 不選 A
```

如果

B = A ⇒ 不

```java
if ret.back() == s[i] 
    ret + s[i]  // 一定只能選 A 

```

所以只有 

```java


// 其他都要
ret + s[i]  // 選 A

if ret.back() != s[i] 
    ret // 不選 A
```

T: O(2^n) in worst

S: O(n), stack depth

class Solution {
    int maxLen;
    public List<String> removeInvalidParentheses(String s) {
        // first use greedy, like leetcode 921 idea, to find result maxLen
        int count = 0;
        int remove = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') { // notice this...
                count--;
            }
            if (count < 0) {
                count = 0;
                remove++;
            }
        }
        remove += count;
        maxLen = s.length() - remove;
        
        List<String> res = new ArrayList<>();

        dfs(res, s, 0, "", 0);
        return res;
    }
    
    
    // i: curr index
    // curStr: current String result
    // count: unmatched count
    
    /*
        use dfs remove duplicate strategy to do dfs
    */
    private void dfs(List<String> res, String s, int i, String curStr, int count) {
        
        // check left: count+, right: count -, so count < 0 means right > left, not valid
        // maxlen is the final Len we caculated before
        if (count < 0 || curStr.length() > maxLen) {
            return;
        }
        // this two if expression can't combine, index will wrong
        if (i == s.length()) { // i go to the string end
            if (count == 0 && curStr.length() == maxLen) {
                res.add(curStr);
            }
            return;
        }
        
        // no bucket, no more for
        
        // add one more next char
        String newStr = curStr + s.charAt(i);
        
        // not '(', ')' , go to next dfs(i+1, newStr, count not change
        if (s.charAt(i) != '(' && s.charAt(i) != ')') {
            dfs(res, s, i+1, newStr, count);
            
        } else { // '(', ')'  case
        // remove duplicate thinking:
        // case 1: curr string last char != add new char
        // case 2: curr string last char == add new char
        // do this, pick next char
        // check one more '(', ')' case, go to next dfs(i+1, newStr, count+1 or count-1
            dfs(res, s, i+1, newStr, count+(s.charAt(i)=='('?1:-1));

            // remove duplicate thinking:
            // curr string last char != add new char
            // don't pick next char
            // go to next dfs(i+1, newStr, count not change
            if (curStr.length() == 0 || curStr.charAt(curStr.length()-1) != s.charAt(i)) {
                dfs(res, s, i+1, curStr, count);
            }
        }
    }
}

/*
T: O(2^n) in worst
S: O(n), stack depth

*/

BFS

T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1).

T: O(n*2^(n-1))

S: O(n)

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        
        if (s == null) {
            return res;
        }
        
        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        
        queue.offer(s);
        visited.add(s);
        
        boolean foundMinRemove = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();

                // find min length string, so set foundMinRemove true
                if (isValid(curr)) { 
                    res.add(curr);
                    foundMinRemove = true;
                }
                // don't need to try to remove more char
                if (foundMinRemove) {
                    continue;
                }
                // gen all pattern, remove one char in origin str to try
                for (int j = 0; j < curr.length(); j++) {
                    if (curr.charAt(j) != '(' && curr.charAt(j) != ')') {
                        continue;
                    }
                    String newStr = curr.substring(0, j) + curr.substring(j+1);
                    if (visited.contains(newStr)) {
                        continue;
                    }
                    queue.offer(newStr);
                    visited.add(newStr);
                }
            }
        }
        return res;
    }
    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

11/30

/*
Return all the possible results. 
so what we can do is brutely using dfs or bfs to remove parentheses
at last, find all the valid results

1. calculate the result maxlen
int count = 0;
int remove = 0;
if (curr == '(')
  count++
else if (curr == ')') {
    count--;
    if (count < 0) {
        count = 0;
        remove++;
    }
}
remove += count;
int maxLen = str.length() - remove;

this can be the validation rule for dfs


2. dfs, how to avoid duplicate, use set to remove duplicate is a way

smarter way is like followings:

((((  ))

2^4 = 16

c(4,2) = 2x3x4/2x2 = 6

ooxx => what we want
oxox
oxxo
xoxo
xxoo
xoox

A new add next char
B cur str's last char

X -> abandon
O -> append

rule:
if (B != A) {
    B dont append anything
    or 
    B.append(A)
}
if (B == A) {
    B.append(A)
}

   A * A * A * A
B  X   X.  X.  X. B
B. X.  X.  X.  A. BA
B. X.  X.  A.     -> if BA, next A must append, because (new add next char is A == cur str's last char is A, A == A
B. X.  X.  A.  A  BAA  => so if we want choose 2 A from 4A, that's the unique way! no duplicate
B. X.  A.  A.  A  BAAA
B. A.  A.  A.  A  BAAAA


B. X.  X.  A.  A  BAA  => so if we want choose 2 A from 4A, that's the unique way! no duplicat


*/

class Solution {
    int maxLen = 0;
    public List<String> removeInvalidParentheses(String s) {
        int count = 0;
        int remove = 0;
        for (char curr : s.toCharArray()) {
            if (curr == '(')
                count++;
            else if (curr == ')') {
                count--;
                if (count < 0) {
                    count = 0;
                    remove++;
                }
            }
        }
        remove += count;
        maxLen = s.length() - remove;
        List<String> res = new ArrayList();
        dfs(res, s, 0, "", 0);
        return res;
    }
    private void dfs(List<String> res, String s, int i, String currStr, int count) {
        if (count < 0 || currStr.length() > maxLen) {
            return;
        }
        if (i == s.length()) {
            if (count == 0 && currStr.length() == maxLen) {
                res.add(currStr);
            }
            return;
        }
        
        String next = s.substring(i, i+1);
        if (s.charAt(i) != '(' && s.charAt(i) != ')') {
            dfs(res, s, i+1, currStr+next, count);
        } else {
            int calCount = (s.charAt(i) == '(') ? 1 : -1;
            dfs(res, s, i+1, currStr+next, count + calCount);

            char nextChar = s.charAt(i);
            if ("".equals(currStr) || currStr.charAt(currStr.length()-1) != nextChar) {
               dfs(res, s, i+1, currStr, count); // dont pick next char
            }
        }
        
    }
}