# 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: [""]


class Solution(object):
    def __init__(self):
        self.misplaced_paranthesis = float('inf')
        self.result = set()
        self.paranthesis = ['(', ')']

    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        self.helper(s, 0, 0, 0, '', 0)
        return list(self.result)

    def helper(self, s, left_count, right_count, removed, valid_string, i):
        if i == len(s):
            if left_count == right_count:
                if removed < self.misplaced_paranthesis:
                    self.result = {valid_string}
                    self.misplaced_paranthesis = removed
                elif removed == self.misplaced_paranthesis:
                    self.result.add(valid_string)
        else:
            if s[i] not in self.paranthesis:
                self.helper(s, left_count, right_count, removed, valid_string + s[i], i + 1)
            else:
                self.helper(s, left_count, right_count, removed + 1, valid_string, i + 1)
                if s[i] == '(':
                    self.helper(s, left_count + 1, right_count, removed, valid_string + s[i], i + 1)
                elif right_count < left_count:
                    self.helper(s, left_count, right_count + 1, removed, valid_string + s[i], i + 1)

# Note:
# https://leetcode.com/articles/remove-invalid-parentheses/
