Watch 10 video solutions for Minimum Insertions to Balance a Parentheses String, a medium level problem involving String, Stack, Greedy. This walkthrough by Fisher Coder has 6,508 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.Problem Overview: You are given a parentheses string where every '(' must be matched with exactly two consecutive ')'. The task is to compute the minimum number of insertions required to make the string valid under this rule.
Approach 1: Stack-based Analysis (O(n) time, O(n) space)
This approach simulates the validation process using a stack. Iterate through the string and push '(' onto the stack. When encountering ')', check whether it forms a pair with the next character to represent the required '))'. If a pair is incomplete, count the insertion needed. The stack tracks unmatched opening brackets and ensures each one receives exactly two closing brackets. This mirrors classical stack-based parenthesis validation but adapts the rule to handle double closing brackets.
Approach 2: Single Pass Counting (Greedy) (O(n) time, O(1) space)
The optimal solution avoids a stack and processes the string using counters. Maintain two variables: one for the number of required closing parentheses (need) and one for insertions performed. Every '(' increases the required closing count by two. If the current requirement becomes odd, insert one ')' to maintain the '))' pairing rule. When encountering ')', decrease the requirement. If the requirement becomes negative, insert an opening bracket before it and reset the needed closing count. This greedy strategy ensures the string stays balanced as you scan left to right using constant memory. The approach relies on careful counting rather than explicit structure tracking and is common in greedy and string parsing problems.
Recommended for interviews: The single-pass greedy counting solution is the expected answer. It runs in O(n) time with O(1) space and demonstrates strong reasoning about invariants while scanning a string. The stack version helps explain the mechanics of matching parentheses, but interviewers usually look for the constant-space greedy insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Analysis | O(n) | O(n) | When explaining matching logic step-by-step or adapting classic stack parenthesis validation |
| Single Pass Counting (Greedy) | O(n) | O(1) | Optimal solution for interviews and large inputs due to constant memory |