'''
keys: https://www.youtube.com/watch?v=2k_rS_u6EBk
Solutions: no dp solution for this one
Similar: 
T:
S:
'''
from typing import List
from collections import deque

class Solution:
    # >>> summary of all solutions
    # https://leetcode.com/problems/remove-invalid-parentheses/discuss/75038/Evolve-from-intuitive-solution-to-optimal-a-review-of-all-solutions


    # >>> bfs since it guarantees shortest path, and we want minimal removal
    # use the same isValid() function
    # https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/share-my-java-bfs-solution
    # T: O(n*2^n), 2^n newstrings, check valid is O(n)
    '''
    Regarding the time complexity, I think one way we can think about the search space
     is as a power subset of the original string. So it includes all possible substrings
      from 0 character to N(number of chars in the input string) characters. So the 
      possibilities are 2^n. (we either pick a character or don't pick it) For each 
      subset we check if it is a valid string so it becomes n*(2^n)
    '''
    def removeInvalidParentheses(self, s: str) -> List[str]:
        q = deque([s])
        res = []
        if not s: return [s] # "" return [""]
        visited = set([s]) # directly using set(s) will split s
        found = False
        while q:
            cur_s = q.popleft()
            if self.isValid(cur_s):
                res.append(cur_s)
                '''cant just use continue here since we need to skip all the rest bfs
                for all pending strings in q. If we continue here, the pending strings in q
                which are not valid will be processed by the below for loop, resulting
                in shorter substrings''' 
                # continue
                found = True
            # # cur_s already valid, further bfs will be sure to have more removals
            # # the pending strings in q are of the same length as cur_s
            # # we have to deal with those first instead of adding more shorter strings
            if found: continue
            # generate all possible states
            for i, c in enumerate(cur_s):
                if c in "()":
                    new_s = cur_s[:i] + cur_s[i+1:]
                    if new_s not in visited:
                        q.append(new_s)
                        visited.add(new_s)
        # print (res)
        return [""] if not res else res


    # >>> dfs
    # https://leetcode.com/problems/remove-invalid-parentheses/discuss/75027/easy-short-concise-and-fast-java-dfs-3-ms-solution
    # remove the first ) in a series of concecutive )s


    # >>>>
    # T: O(n^(l+r))
    # S: O((l+r)^2)
    def isValid(self, s):
        ct = 0
        for c in s:
            if c == "(": ct +=1 
            if c == ")": ct -= 1
            if ct < 0: return False
        return ct == 0
    
    def dfs(self, s, start, l, r):
        if l == 0 and r == 0:
            if self.isValid(s):
                self.ans.append(s)
                return
        
        for i in range(start, len(s)):
            if i != start and s[i] == s[i-1]:
                continue # We only remove the first parenthes if there are consecutive ones to avoid duplications.
            
            if s[i] == "(" or s[i] == ")":
                curr = s
                curr = curr[:i] + curr[i+1:] # remove c at index i
                if r > 0 and s[i] == ")":
                    self.dfs(curr, i, l, r-1)
                elif l > 0 and s[i] == "(":
                    self.dfs(curr, i, l-1, r)
                    
    def removeInvalidParentheses0(self, s: str) -> List[str]:
        l, r = 0, 0
        for c in s:
            l += (c == "(") # ct of left parentheses
            if l == 0: # no remaining left parentheses
                r += (c == ")") # ct of single right parenthese
            else: # with remaining left parentheses
                l -= (c == ")") # cancelling pairs
        
        self.ans = []
        self.dfs(s, 0, l, r)
        return self.ans


            
sol = Solution()
print (sol.removeInvalidParentheses("()())()"))
# print (sol.removeInvalidParentheses(")(f"))
        
        
        
        
