[LeetCode] 301. Remove Invalid Parentheses

 Problem : https://leetcode.com/problems/remove-invalid-parentheses/

Iterating the input string from left right,  for each bracket, we have 2 options. Either keep this bracket or remove this bracket from the final expression. In the end, check the expression is valid by verify if opening bracket == closing bracket. Use removedCount to track how many bracket be removed from the final expression.  Only save the expression with minimal removal count.

Time Complexity = O ( 2 ** N ).     ( As for each character we can choose either keep or remove it from the final expression. )

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.result = set()
        self.minRemoved = 2 ** 31 - 1
        
        def helper(index, leftCount, rightCount, expression, removedCount):
            
            if index == len(s):
                if leftCount == rightCount:
                    if removedCount < self.minRemoved:
                        self.result = set([expression])
                        self.minRemoved = removedCount
                    elif removedCount == self.minRemoved:
                        self.result.add(expression)
            else:
                if s[index] not in '()':
                    helper(index + 1, leftCount, rightCount, expression + s[index], removedCount)
                else:
                    # remove this bracket
                    helper(index + 1, leftCount, rightCount, expression, removedCount + 1)
                    
                    # keep this bracket
                    if s[index] == '(':
                        helper(index + 1, leftCount + 1, rightCount, expression + s[index], removedCount)
                    elif rightCount < leftCount:
                        # only keep closing bracket when right < left
                        helper(index + 1, leftCount, rightCount + 1, expression + s[index], removedCount)
        
        
        helper(0, 0, 0, '', 0)
        return self.result

Limited Backtracking:

This algorithm is faster because it only remove the misplaced parentheses.

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        misplacedLeft = misplacedRight = 0
        
        # find all misplaced parentheses 
        for i in range(len(s)):
            if s[i] == '(':
                misplacedLeft += 1
            elif s[i] == ')':
                if misplacedLeft > 0:
                    misplacedLeft -= 1
                else:
                    misplacedRight += 1
        
        # note: use hash set to avoid duplicate result
        result = set()
        
        def helper(left, right, leftToRemove, rightToRemove, index, tmp):
            if index == len(s):
                if leftToRemove == 0 and rightToRemove == 0:
                    # tmp is valid because all misplaced parentheses have been removed
                    result.add(tmp)
            else:
                if s[index] == '(':
                    if leftToRemove > 0:
                        # remove one misplaced 'left' parenthesis
                        helper(left, right, leftToRemove - 1, rightToRemove, index + 1, tmp)

                    # keep the 'left' parenthesis
                    # note: increase the 'left' counter
                    helper(left + 1, right, leftToRemove, rightToRemove, index + 1, tmp + '(')
                elif s[index] == ')':
                    if rightToRemove > 0:
                        # remove one misplaced 'right' parenthesis
                        helper(left, right, leftToRemove, rightToRemove - 1, index + 1, tmp)

                    if left > right:
                        # keep the 'right' parenthesis if it can still maintain a valid string
                        # note : increase the 'right' counter
                        helper(left, right + 1, leftToRemove, rightToRemove, index + 1, tmp + ')')
                else:
                    # keep all letters
                    helper(left, right, leftToRemove, rightToRemove, index + 1, tmp + s[index])
        
        helper(0, 0, misplacedLeft, misplacedRight, 0, '')
        return result