Minimum Remove to Make Valid Parentheses

Problem

Remove the minimum number of parentheses so the string is valid. Return any valid result.

Example

s = "a)b(c)d"
Output: "ab(c)d"

Constraints

• 1 ≤ s.length ≤ 10^5

Approach

Stack of indices for '('; mark unmatched ')' and leftover '(' for removal. A Meta phone-screen staple.