277. Minimum Insertions to Balance Parentheses

Given a parentheses string s, a balanced string requires every '(' to be matched by two consecutive ')'. Return the minimum number of insertions (of '(' or ')') needed to make s balanced.

Input: A quoted parentheses string.

Output: Integer — minimum insertions.

Examples

Input: "(()))"
Output: 1
Explanation: One insertion balances it.

Input: "())"
Output: 0
Explanation: Already balanced: one '(' with two ')'.

Input: "(((((("
Output: 12
Explanation: Each '(' needs '))'.

Constraints

• 1<=s.length<=10^5
• s[i] in {'(',')'}

Asked by