635. Minimum Add to Make Parentheses Valid

Given a string s of '(' and ')', return the minimum number of parentheses (of either type) that must be inserted anywhere so the result is a valid balanced string. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the minimum insertions needed.

Examples

Input: {"s":"())"}
Output: 1
Explanation: Add one '(' at the front.

Input: {"s":"((("}
Output: 3
Explanation: Need three closings.

Input: {"s":"()()"}
Output: 0
Explanation: Already valid.

Constraints

• 0<=|s|<=1000

Asked by