# Ugly 52ms python solution

• ``````class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
lmore = 0
rmore = 0
lidx = []
ridx = []
count = 0
for i in range(len(s)):
if s[i] == '(':
count += 1
elif s[i] == ')':
count -= 1
if count < 0:
rmore += 1
count = 0
ridx.append(i)
if count > 0:
lmore = count
if lmore == 0 and rmore == 0: return [s]

# case1: only ')' is more than '('.
if rmore > 0 and lmore == 0:
result = set()
self.removeRight(result, s[:ridx[-1]+1], rmore, rmore, ridx, 0)
return [l+s[ridx[-1]+1:] for l in list(result)]

count = 0
for i in range(-1,-len(s)-1,-1):
if s[i] == ')':
count += 1
elif s[i] == '(':
count -= 1
if count < 0:
count = 0
lidx.append(i)
# case2: only '(' is more than ')'.
if lmore > 0 and rmore == 0:
result = set()
self.removeLeft(result, s[lidx[-1]:], lmore, lmore, lidx, -1)
return [s[:lidx[-1]]+l for l in list(result)]

# case3: in first interval, ')' is more than '('; in second interval, '(' is more than ')'.
if lmore > 0 and rmore > 0:
result1 = set()
self.removeRight(result1, s[:ridx[-1]+1], rmore, rmore, ridx, 0)
result2 = set()
self.removeLeft(result2, s[lidx[-1]:], lmore, lmore, lidx, -1)
return [l1+s[ridx[-1]+1:lidx[-1]]+l2 for l1 in list(result1) for l2 in list(result2)]

def removeRight(self, result, s, c, n, ridx, idx):
if n == 0:
return
for i in range(idx, ridx[0]+1-c+n):
if s[i] == ')':
ns = s[:i]+s[i+1:]
self.removeRight(result, ns, c, n-1, ridx[1:], i)

def removeLeft(self, result, s, c, n, lidx, idx):
if n == 0: