Remove Invalid Parentheses | Hard

- Use DFS to recursively either remove the character or just continue.

- The program expects empty string in the answer if there are no other matches
- non-parenthesis characters is like a no-op character, that moves the iterator without doing anything.
- The answer needs to be in set to avoid duplicates
- left parenthesis(L) has a preferential consideration over right parenthesis(R) since R is an invariant if there is more R than L at any given position.

- The resulting answer should have a matching number of parenthesis.
- Iteration ends when the iteration reaches the end of the string

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        ans = set()
        N = len(s)
        length = 0
        def traverse(left, right, i, stack):
            nonlocal s, ans, N, length
            if i == N:
                if stack and left == 0 and right == 0: #3
                    if len(stack) > length:
                        ans = {stack}
                        length = len(stack)
                    elif len(stack) == length:
                        ans.add(stack)
            else:

                if s[i] == '(':
                    if right==0:
                        traverse(left+1, right, i+1, stack+s[i])
                    traverse(left, right, i+1, stack)
                elif s[i] == ')':
                    if left > 0:
                        traverse(left-1, right, i+1, stack+s[i])
                    traverse(left, right, i+1, stack) 
                else:
                    traverse(left, right, i+1, stack+s[i])
        traverse(0,0,0,"")
        return ans or [""] #1

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        ans = set()
        N = len(s)
        left_rem, right_rem = 0, 0
        for i in range(N):
            if s[i] == '(':
                left_rem +=1        # Preferential treatment of L
            elif s[i] == ')':
                if left_rem > 0:
                    left_rem -= 1
                else:
                    right_rem += 1

        def dfs(i, left, right, left_rem, right_rem, stack):
            nonlocal ans
            if i == N:
                if left_rem == 0 and right_rem == 0:
                    ans.add(stack)
                return
            else:
                if s[i] == "(":
                    if left_rem > 0:   
                        dfs(i+1, left, right, left_rem-1, right_rem, stack)
                    # Preferential treatment of L. No condition for considering it
                    dfs(i+1, left+1, right, left_rem, right_rem, stack+s[i])
                elif s[i] == ")":
                    if right_rem > 0:
                        dfs(i+1, left, right, left_rem, right_rem-1, stack)
                    if left > right:
                        dfs(i+1, left, right+1, left_rem, right_rem, stack+s[i])
                else:
                    dfs(i+1, left, right, left_rem, right_rem, stack+s[i])
        dfs(0,0,0,left_rem,right_rem,"")
        return ans