Remove Invalid Parentheses

Problem: Remove Invalid Parentheses

The general idea is simple, we just try to remove every possible parentheses which makes the string invalid. However we need to do some optimization. Some basic idea is that we can calculate how many parentheses we need to remove. This number can be calculated by unpaired parentheses.

Code in Python:

from collections import deque

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ans = []
        def valid_degree(string):
            stack = []
            count = 0
            for c in string:
                if c == "(": stack.append(1)
                elif c == ")" and stack: stack.pop()
                elif c == ")": count += 1
            return count + len(stack)


        candidates = []
        def helper(start, n, removed):
            if len(removed) != n:
                for i in xrange(start, len(candidates)):
                    if i > start and candidates[i] == candidates[i-1]+1 and s[candidates[i]] == s[candidates[i-1]]: continue
                    helper(i+1, n, removed+[candidates[i]])
            else:
                string = s[:removed[0]]
                for i in xrange(1, n):
                    string += s[removed[i-1]+1:removed[i]]
                string += s[removed[n-1]+1:]
                if not valid_degree(string): ans.append(string)

        degree = valid_degree(s)
        if not degree: return [s]
        for i, c in enumerate(s):
            if c == "(" or c == ")": candidates.append(i)
        helper(0, degree, [])
        return ans