<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def removeInvalidParentheses ( self , s ) : <EOL> """<STR_LIT>""" <EOL> rmcnt = self . minrm ( s ) <EOL> ret = [ ] <EOL> self . dfs ( s , "<STR_LIT>" , <NUM_LIT:0> , None , <NUM_LIT:0> , rmcnt , ret ) <EOL> return ret <EOL> def minrm ( self , s ) : <EOL> """<STR_LIT>""" <EOL> rmcnt = <NUM_LIT:0> <EOL> left = <NUM_LIT:0> <EOL> for c in s : <EOL> if c == "<STR_LIT:(>" : <EOL> left += <NUM_LIT:1> <EOL> elif c == "<STR_LIT:)>" : <EOL> if left > <NUM_LIT:0> : <EOL> left -= <NUM_LIT:1> <EOL> else : <EOL> rmcnt += <NUM_LIT:1> <EOL> rmcnt += left <EOL> return rmcnt <EOL> def dfs ( self , s , cur , left , pi , i , rmcnt , ret ) : <EOL> """<STR_LIT>""" <EOL> if left < <NUM_LIT:0> or rmcnt < <NUM_LIT:0> or i > len ( s ) : <EOL> return <EOL> if i == len ( s ) : <EOL> if rmcnt == <NUM_LIT:0> and left == <NUM_LIT:0> : <EOL> ret . append ( cur ) <EOL> return <EOL> if s [ i ] not in ( "<STR_LIT:(>" , "<STR_LIT:)>" ) : <EOL> self . dfs ( s , cur + s [ i ] , left , None , i + <NUM_LIT:1> , rmcnt , ret ) <EOL> else : <EOL> if pi == s [ i ] : <EOL> while i < len ( s ) and pi and pi == s [ i ] : i , rmcnt = i + <NUM_LIT:1> , rmcnt - <NUM_LIT:1> <EOL> self . dfs ( s , cur , left , pi , i , rmcnt , ret ) <EOL> else : <EOL> self . dfs ( s , cur , left , s [ i ] , i + <NUM_LIT:1> , rmcnt - <NUM_LIT:1> , ret ) <EOL> L = left + <NUM_LIT:1> if s [ i ] == "<STR_LIT:(>" else left - <NUM_LIT:1> <EOL> self . dfs ( s , cur + s [ i ] , L , None , i + <NUM_LIT:1> , rmcnt , ret ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> assert Solution ( ) . removeInvalidParentheses ( "<STR_LIT>" ) == [ '<STR_LIT>' , '<STR_LIT>' ] </s>
