Learning On the Way

301. Remove Invalid Parentheses

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all the possible results. You may return the answer in any order.

def removeInvalidParentheses(self, s: str) -> List[str]: 
    score = collections.defaultdict(int) 
    score['('], score[')'] = 1, -1 
     
    def findNumberToRemove(s): 
        cum = 0 
        lowest = 0 
        for c in s: 
            cum += score[c] 
            lowest = min(lowest, cum) 
        return cum + abs(lowest), abs(lowest) 
     
    curstr = [] 
    curscore = 0 
    res = set() 
     
    leftmax, rightmax = findNumberToRemove(s) 
     
    def backtrack(start):     
        nonlocal curscore, leftmax, rightmax 
        if curscore < 0: 
            return 
         
        if start == len(s): 
            if leftmax == rightmax == 0: 
                res.add(''.join(curstr)) 
            return 
         
        c = s[start] 
        if c == '(' and leftmax > 0: 
            leftmax -= 1 
            backtrack(start + 1) 
            leftmax += 1 
             
        if c == ')' and rightmax > 0: 
            rightmax -= 1 
            backtrack(start + 1) 
            rightmax += 1 
             
        curstr.append(c) 
        curscore += score[c] 
        backtrack(start + 1) 
        curstr.pop() 
        curscore -= score[c] 
         
    backtrack(0) 
    return list(res)