Minimum Add to Make Parentheses Valid

Medium · Stack & Monotonic Stack · about 10 minutes

Asked at Meta, Google, Amazon, Microsoft.

Given a string s of '(' and ')', return the minimum number of parentheses you must insert (anywhere) to make it valid.