Watch 10 video solutions for Minimum Insertions to Balance a Parentheses String, a medium level problem involving String, Stack, Greedy. This walkthrough by NeetCode has 475,216 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
'(' must have a corresponding two consecutive right parenthesis '))'.'(' must go before the corresponding two consecutive right parenthesis '))'.In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.
"())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.You can insert the characters '(' and ')' at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.
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 '('.
Constraints:
1 <= s.length <= 105s consists of '(' and ')' only.