Medium

Minimum Remove to Make Valid Parentheses

LAB

Remove the fewest parentheses to make s valid and return the resulting string.

EXAMPLES

Example 1

Input
{
  "s": "lee(t(c)o)de)"
}

Output
"lee(t(c)o)de"

FUNCTION SHAPE

s: string→string

SOLUTION NOTE

Track indices of unmatched brackets. Need stack (not counter) to know which indices to remove.

Reveal reference solution +

pythonREFERENCE

def minRemoveToMakeValid(self, s: str) -> str:
    remove = set()
    stack = []
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            if stack:
                stack.pop()
            else:
                remove.add(i)
    remove.update(stack)
    return ''.join(c for i, c in enumerate(s) if i not in remove)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗