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

Example 1:

Input: "()())()" 
Output: ["()()()", "(())()"] 

Example 2:

Input: "(a)())()" 
Output: ["(a)()()", "(a())()"] 

Example 3:

Input: ")(" 
Output: [""]

Idea – 1

If we have n open/close parentheses, we could try each of possibilities and group the valid ones by length. Then the valid group with the longest length would be our solution. Time complexity and space complexity .

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        HashMap<Integer, HashSet<String>> map = new HashMap<>();
        collect(s, 0, "", map);
        
        int max = 0;
        for(int k : map.keySet())
        {
            max = Math.max(max, k);
        }
        
        return new ArrayList<String>(map.get(max));
    }
    
    private void collect(String s, int i, String curr, HashMap<Integer, HashSet<String>> ans)
    {
        if(i >= s.length())
        {
            if(valid(curr))
            {
                HashSet<String> grp = ans.getOrDefault(curr.length(), new HashSet<>());
                grp.add(curr);
                ans.put(curr.length(), grp);
            }
            
            return;
        }
        
        char c = s.charAt(i);
        
        if(Character.isLetter(c))
        {
            collect(s, i+1, curr+c, ans);
        }
        else
        {
            collect(s, i+1, curr, ans);
            collect(s, i+1, curr+c, ans);
        }
    }
    
    private boolean valid(String candidate)
    {
        int n = candidate.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = candidate.charAt(i);
            if(c == '(')
            {
                stack.addLast(c);
            }
            else if(c == ')')
            {
                if(stack.isEmpty())
                {
                    return false;
                }
                
                char top = stack.removeLast();
                if(top != '(')
                {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


Runtime: 246 ms, faster than 5.01% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 44.5 MB, less than 17.57% of Java online submissions for Remove Invalid Parentheses.

Idea - 2

Since we need to delete min number of parentheses to make it valid, we can consider the output of deleting a parenthesis as a neighbor of current string and thus a BFS would give us the result, actually all valids in an entire level of BFS. Say the input has n characters in it, then it would produce n neighbors each having length n-1, each of these neighbors would produce n-1 neighbors having length n-2, etc. So the time complexity is and space would be .

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        HashSet<String> set = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        
        Deque<String> q = new ArrayDeque<>();
        q.addLast(s);
        visited.add(s);
        
        boolean found = false;
        while(!q.isEmpty())
        {
            int n = q.size();
            while(n-- > 0)
            {
                String front = q.removeFirst();
                if(valid(front))
                {
                    set.add(front);
                    found = true;
                }
                
                if(!found)
                {
                    for(int i = 0; i < front.length(); ++i)
                    {
                        if(Character.isLetter(front.charAt(i)))
                        {
                            continue;
                        }
                        
                        String nei = front.substring(0, i) + front.substring(i+1);
                        if(!visited.contains(nei))
                        {
                            visited.add(nei);
                            q.addLast(nei);
                        }
                    }
                }
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    private boolean valid(String candidate)
    {
        int n = candidate.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = candidate.charAt(i);
            if(c == '(')
            {
                stack.addLast(c);
            }
            else if(c == ')')
            {
                if(stack.isEmpty())
                {
                    return false;
                }
                
                char top = stack.removeLast();
                if(top != '(')
                {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


Runtime: 52 ms, faster than 36.58% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 41.6 MB, less than 36.73% of Java online submissions for Remove Invalid Parentheses.