#1541
Minimum Insertions to Balance a Parentheses String
specialist · 835 · lc medium +31 · verified · 53.5% accepted · 1,261 likes · top 45%
Description
A parentheses string uses a special rule: each '(' must be matched by exactly two consecutive ')' characters. Given a string s containing only '(' and ')', you may insert characters anywhere to make it balanced under this rule. Return the minimum number of insertions required.
Example 1:
Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to add one more ')' at the end of the string to be "(())))" which is balanced.
Example 2:
Input: s = "())"
Output: 0
Explanation: The string is already balanced.
Example 3:
Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
Code
1
2
3