remove invalid parentheses

🏠

Credit: Stephan Pochmann

 1 def removeInvalidParentheses(s):
 2     def isvalid(s):
 3         ctr = 0
 4         for c in s:
 5             ctr += (c == "(") - (c == ")")
 6             if ctr < 0:
 7                 return False
 8         return ctr == 0
 9 
10     level = {s}
11     while True:
12         valid = [*filter(isvalid, level)]
13         if valid:
14             return valid
15         level = {s[:i] + s[i + 1 :] for s in level for i in range(len(s))}
16 
17 
18 r = removeInvalidParentheses("(a)())()")
19 print(r)
20 
21 ["(a)()()", "(a())()"]