Basically, we want to keep all letters, but if we see a (, append it to a dictionary and keep its location. If we see a ’)’, then we want to keep the left paren and the right paren if there is a matching previous open paren.
At the end, we drop all left and right parens that don’t match, and join the string according to the dictionary that tells us if we should keep the character.
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
keep = defaultdict(bool)
stack = []
for i, c in enumerate(s):
if c not in '()':
keep[i] = True
continue
if c == '(':
stack.append(i)
continue
if c == ')':
if stack:
left_paren_i = stack.pop()
keep[left_paren_i] = True
keep[i] = True
return ''.join(c for i, c in enumerate(s) if keep[i])