Minimum Remove to Make Valid Parentheses

Medium · Stack & Monotonic Stack · about 15 minutes

Asked at Meta, Bloomberg, Amazon, Google, Microsoft.

Given a string s of lowercase letters and '(' / ')', remove the minimum number of parentheses so the result is valid (every '(' has a matching later ')').

Several strings can be minimal, so return this one: pair the brackets the standard way (each ')' matches the nearest unpaired '(' before it) and remove exactly the brackets left unpaired.