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.
In this approach, we'll keep track of the unmatched left parentheses '(' and needed right parentheses ')'. As we traverse the string, we'll adjust our counters based on the current character.
At the end, the sum of remaining left needs to be paired with ''))'' and any unmatched right will give us the total number of insertions required.
This solution efficiently counts the number of insertions required by simulating the operation of the string as per balanced requirements. The main work is done in a single pass through the string.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), using constant space for variables.
We can solve this using a stack to better visualize the process of seeing parenthesis as matched pairs. By pushing and popping elements, we simulate the pairing of '(' with '))'.
Use a stack data structure to manage leftover unmatched '(' parenthesis while iterating over the string to determine the complement needed for each unmatched pair.
This solution efficiently uses a stack to count how many unmatched opening brackets remain, ensuring that at the end, any remaining stack elements are properly complemented with closing brackets. For each traversed character, appropriate stack operations determine the minimum insertions required.
Time Complexity: O(n), due to a single pass through the string.
Space Complexity: O(n), maximum stack space needed for unmatched '('.
| Approach | Complexity |
|---|---|
| Single Pass Counting | Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), using constant space for variables. |
| Stack-based Analysis | Time Complexity: O(n), due to a single pass through the string. Space Complexity: O(n), maximum stack space needed for unmatched '('. |
| Default Approach | — |
| 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 |
LeetCode 1541. Minimum Insertions to Balance a Parentheses String - Interview Prep Ep 88 • Fisher Coder • 6,508 views views
Watch 9 more video solutions →Practice Minimum Insertions to Balance a Parentheses String with our built-in code editor and test cases.
Practice on FleetCode