# Credit: # Credit: https://leetcode.com/problems/remove-invalid-parentheses/discuss/186597/Very-easy-to-understand-Python-DFS
class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        self.left_to_right(s, res, 0, 0)
        return res

    # Remove extra ")"s
    def left_to_right(self, s, res, i_start, j_search_start):
        """
        scan from left to right, remove surplus ')'
        """
        # DFS
        count = 0
        for i in range(i_start, len(s)):
            if s[i] == '(':  # '('
                count += 1
            if s[i] == ')':  # ')'
                count -= 1
            # Do nothing if it's neither ')' or '('

            if count < 0:
                # search for ')'
                for j in range(j_search_start, i + 1):  # j_search_start ~ i
                    if s[j] == ')' \
                            and ((j == j_search_start) or s[j - 1] != s[j]):  # remove the first ')' among consecutive ones
                        print('i: %d, j: %d'%(i,j))
                        # remove s[j] and continue searching
                        char_removed = s[:j] + s[j+1:]
                        self.left_to_right(char_removed, res, i,j)
                return  # only search in the char_removed substring

        # if finished removing suplus ')' by scanning left to right,
        # scan for '(' right to left
        self.right_to_left(s, res, len(s)-1, len(s)-1)

    # Remove extra "("s
    def right_to_left(self, s, res, i_start, j_search_start):
        """
        scan from right to left, remove surplus '('
        append result to res
        """
        # DFS
        count = 0
        for i in range(i_start, -1, -1):  # i_start~0
            if s[i] == ')':  # ')
                count += 1
            if s[i] == '(':  # '(
                count -= 1
            # Do nothing if it's neither ')' or '('
            if count < 0:
                # search for '('
                for j in range(j_search_start, i-1, -1):  # i ~ j_search_start
                    if s[j] == '(' \
                            and ((j == j_search_start) or s[j+1] != s[j]):
                        # remove the first ')' among consecutive ones (when scanning from right to left)
                        # remove s[j] and continue searching
                        char_removed = s[:j] + s[j+1:]
                        self.right_to_left(char_removed, res, i-1,j-1)
                return

        # base case: finished scanning
        print('found %s'%s)
        res.append(s)