Remove Invalid Parentheses

Source

• leetcode: Remove Invalid Parentheses

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 ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Java

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        Set<String> res = new HashSet<>();
        int l = 0, r = 0;
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i) == '(') l++;
            if(s.charAt(i) == ')') {
                if(l != 0) l--;
                else r++;
            }
        }
        DFS(res, s, 0, l, r, 0, new StringBuilder());
        return new ArrayList<String>(res);  
    }

    public void DFS(Set<String> res, String s, int pos, int l, int r, int open, StringBuilder sb) {
        if(pos==s.length() && l==0 && r==0 && open==0) {
            res.add(sb.toString());
            return;
        }
        if(pos==s.length() || l<0 || r<0 || open<0) return;

        char c = s.charAt(pos);
        int len = sb.length();

        if(c == '(') {
            DFS(res, s, pos+1, l-1, r, open, sb);
            DFS(res, s, pos+1, l, r, open+1, sb.append(c)); 

        } else if(c == ')') {
            DFS(res, s, pos+1, l, r-1, open, sb);
            DFS(res, s, pos+1, l, r, open-1, sb.append(c));

        } else {
            DFS(res, s, pos+1, l, r, open, sb.append(c)); 
        }

        sb.setLength(len);
    }
}

Reference

Easiest 9ms Java Solution