Minimum Insertions to Balance a Parentheses String - Video Solutions
LeetCode 1541. Minimum Insertions to Balance a Parentheses String - Interview Prep Ep 88
Minimum Insertions to Balance a Parentheses String - Video Solution
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,628 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
- Any left parenthesis
'('must have a corresponding two consecutive right parenthesis'))'. - Left parenthesis
'('must go before the corresponding two consecutive right parenthesis'))'.
In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.
- For example,
"())","())(())))"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 <= 105sconsists of'('and')'only.
Approach Overview
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.
Complexity Analysis
| 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 |