public List<String> removeInvalidParentheses(String s) {

Set<String> results = new HashSet<>();

int L = s.length();

if (L == 0) return Arrays.asList("");

Stack<Character> st = new Stack<>();

StringBuilder sb = new StringBuilder("");

int maxLength = helper(s, 0, st, sb, L, results);

return setToList(results, maxLength);

}

private int helper(String s, int level, Stack<Character> st, StringBuilder sb, int L, Set<String> results) {

int maxLength = 0;

if (level == L) {

if (st.size() == 0) {

maxLength = Math.max(maxLength, sb.length());

results.add(sb.toString());

}

return maxLength;

}

char c = s.charAt(level);

int localMax = 0;

if (c >= 'a' && c <= 'z') {

sb.append(c);

localMax = helper(s, level+1, st, sb, L, results);

maxLength = Math.max(maxLength, localMax);

sb.deleteCharAt(sb.length()-1);

} else if (c == '(') {

st.push('(');

sb.append('(');

localMax = helper(s, level+1, st, sb, L, results);

maxLength = Math.max(maxLength, localMax);

st.pop();

sb.deleteCharAt(sb.length()-1);

localMax = helper(s, level+1, st, sb, L, results);

maxLength = Math.max(maxLength, localMax);

} else if (c == ')' && !st.empty() && st.peek() == '(') {

st.pop();

sb.append(c);

localMax = helper(s, level+1, st, sb, L, results);

maxLength = Math.max(maxLength, localMax);

st.push('(');

sb.deleteCharAt(sb.length()-1);

localMax = helper(s, level+1, st, sb, L, results);

maxLength = Math.max(maxLength, localMax);

} else {

localMax = helper(s, level+1, st, sb, L, results);

maxLength = Math.max(maxLength, localMax);

}

return maxLength;

}

private List<String> setToList(Set<String> set, int maxLength) {

List<String> results = new ArrayList<>();

for (String s: set) {

if (s.length() == maxLength) {

results.add(s);

}

}

return results;

}

/**

public List<String> removeInvalidParentheses2(String s) {

List<String> ans = new ArrayList<>();

remove(s, ans, 0, 0, new char[]{'(', ')'});

return ans;

}

public void remove(String s, List<String> ans, int last_i, int last_j, char[] par) {

for (int stack = 0, i = last_i; i < s.length(); ++i) {

if (s.charAt(i) == par[0]) stack++;

if (s.charAt(i) == par[1]) stack--;

if (stack >= 0) continue;

for (int j = last_j; j <= i; ++j)

if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))

remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);

return;

}

String reversed = new StringBuilder(s).reverse().toString();

if (par[0] == '(') // finished left to right

remove(reversed, ans, 0, 0, new char[]{')', '('});

else // finished right to left

ans.add(reversed);

}

/**

public List<String> removeInvalidParentheses3(String s) {

List<String> res = new ArrayList<>();

// sanity check

if (s == null) return res;

Set<String> visited = new HashSet<>();

Queue<String> queue = new LinkedList<>();

// initialize

queue.add(s);

visited.add(s);

boolean found = false;

while (!queue.isEmpty()) {

s = queue.poll();

if (isValid(s)) {

// found an answer, add to the result

res.add(s);

found = true;

}

if (found) continue;

// generate all possible states

for (int i = 0; i < s.length(); i++) {

// we only try to remove left or right paren

if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;

String t = s.substring(0, i) + s.substring(i + 1);

if (!visited.contains(t)) {

// for each state, if it's not visited, add it to the queue

queue.add(t);

visited.add(t);

}

}

}

return res;

}

// helper function checks if string s contains valid parantheses

boolean isValid(String s) {

int count = 0;

for (int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

if (c == '(') count++;

if (c == ')' && count-- == 0) return false;

}

return count == 0;

}

/**

public List<String> removeInvalidParentheses4(String s) {

int rmL = 0, rmR = 0;

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') {

rmL++;

} else if (s.charAt(i) == ')') {

if (rmL != 0) {

rmL--;

} else {

rmR++;

}

}

}

Set<String> res = new HashSet<>();

dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);

return new ArrayList<String>(res);

}

public void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open) {

if (rmL < 0 || rmR < 0 || open < 0) {

return;

}

if (i == s.length()) {

if (rmL == 0 && rmR == 0 && open == 0) {

res.add(sb.toString());

}

return;

}

char c = s.charAt(i);

int len = sb.length();

if (c == '(') {

dfs(s, i + 1, res, sb, rmL - 1, rmR, open); // not use (

dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1); // use (

} else if (c == ')') {

dfs(s, i + 1, res, sb, rmL, rmR - 1, open); // not use )

dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1); // use )

} else {

dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);

}

sb.setLength(len);

}

/**

public List<String> removeInvalidParentheses5(String s) {

int count = 0, openN = 0, closeN = 0;

// calculate the total numbers of opening and closing parentheses

// that need to be removed in the final solution

for (char c : s.toCharArray()) {

if (c == '(') {

count++;

} else if (c == ')') {

if (count == 0) closeN++;

else count--;

}

}

openN = count;

count = 0;

if (openN == 0 && closeN == 0) return Arrays.asList(s);

List<String> result = new ArrayList<>();

StringBuilder sb = new StringBuilder();

dfs(s.toCharArray(), 0, count, openN, closeN, result, sb);

return result;

}

private void dfs(char[] s, int p, int count, int openN, int closeN, List<String> result, StringBuilder sb) {

if (count < 0) return; // the parentheses is invalid

if (p == s.length) {

if (openN == 0 && closeN == 0) { // the minimum number of invalid parentheses have been removed

result.add(sb.toString());

}

return;

}

if (s[p] != '(' && s[p] != ')') {

sb.append(s[p]);

dfs(s, p + 1, count, openN, closeN, result, sb);

sb.deleteCharAt(sb.length() - 1);

} else if (s[p] == '(') {

int i = 1;

while (p + i < s.length && s[p + i] == '(') i++; // use while loop to avoid duplicate result in DFS, instead of using HashSet

sb.append(s, p, i);

dfs(s, p + i, count + i, openN, closeN, result, sb);

sb.delete(sb.length() - i, sb.length());

if (openN > 0) {

// remove the current opening parenthesis

dfs(s, p + 1, count, openN - 1, closeN, result, sb);

}

} else {

int i = 1;

while (p + i < s.length && s[p + i] == ')') i++; // use while loop to avoid duplicate result in DFS, instead of using HashSet

sb.append(s, p, i);

dfs(s, p + i, count - i, openN, closeN, result, sb);

sb.delete(sb.length() - i, sb.length());

if (closeN > 0) {

// remove the current closing parenthesis

dfs(s, p + 1, count, openN, closeN - 1, result, sb);

}

}

}