Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
- Any left parenthesis
'('has a corresponding right parenthesis')'. - Left parentheses
'('must go before the corresponding right parentheses')'. '*'could be treated as a single right parenthesis')'or a single left parenthesis'('or an empty string.
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 <= 10^5
- s[i] is either
'('or')'.
Approach 1: Greedy with Counter
Algorithm
- Use a counter to track unmatched left parentheses
- For each character:
- If
'(', increment counter - If
')', decrement counter - If counter becomes negative, we need to add a
'('
- If
- At the end, add
')'for each remaining unmatched'('
Solution
Python:
def minInsertions(s):
"""
Greedy approach with counter
Time: O(n) - single pass through string
Space: O(1) - constant extra space
"""
insertions = 0
left_count = 0
i = 0
while i < len(s):
if s[i] == '(':
left_count += 1
else: # s[i] == ')'
if i + 1 < len(s) and s[i + 1] == ')':
# Found "))"
if left_count > 0:
left_count -= 1
else:
# Need to add '('
insertions += 1
i += 1 # Skip next ')'
else:
# Found single ')'
if left_count > 0:
left_count -= 1
insertions += 1 # Need to add another ')'
else:
# Need to add '(' and ')'
insertions += 2
i += 1
# Add ')' for remaining unmatched '('
insertions += left_count * 2
return insertions
Java:
class Solution {
/**
* Greedy approach with counter
* Time: O(n) - single pass through string
* Space: O(1) - constant extra space
*/
public int minInsertions(String s) {
int insertions = 0;
int leftCount = 0;
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == '(') {
leftCount++;
} else { // s.charAt(i) == ')'
if (i + 1 < s.length() && s.charAt(i + 1) == ')') {
// Found "))"
if (leftCount > 0) {
leftCount--;
} else {
// Need to add '('
insertions++;
}
i++; // Skip next ')'
} else {
// Found single ')'
if (leftCount > 0) {
leftCount--;
insertions++; // Need to add another ')'
} else {
// Need to add '(' and ')'
insertions += 2;
}
}
}
i++;
}
// Add ')' for remaining unmatched '('
insertions += leftCount * 2;
return insertions;
}
}
Go:
// minInsertions - Greedy approach with counter
// Time: O(n) - single pass through string
// Space: O(1) - constant extra space
func minInsertions(s string) int {
insertions := 0
leftCount := 0
i := 0
for i < len(s) {
if s[i] == '(' {
leftCount++
} else { // s[i] == ')'
if i+1 < len(s) && s[i+1] == ')' {
// Found "))"
if leftCount > 0 {
leftCount--
} else {
// Need to add '('
insertions++
}
i++ // Skip next ')'
} else {
// Found single ')'
if leftCount > 0 {
leftCount--
insertions++ // Need to add another ')'
} else {
// Need to add '(' and ')'
insertions += 2
}
}
}
i++
}
// Add ')' for remaining unmatched '('
insertions += leftCount * 2
return insertions
}
JavaScript:
/**
* Greedy approach with counter
* Time: O(n) - single pass through string
* Space: O(1) - constant extra space
*/
function minInsertions(s) {
let insertions = 0;
let leftCount = 0;
let i = 0;
while (i < s.length) {
if (s[i] === '(') {
leftCount++;
} else { // s[i] === ')'
if (i + 1 < s.length && s[i + 1] === ')') {
// Found "))"
if (leftCount > 0) {
leftCount--;
} else {
// Need to add '('
insertions++;
}
i++; // Skip next ')'
} else {
// Found single ')'
if (leftCount > 0) {
leftCount--;
insertions++; // Need to add another ')'
} else {
// Need to add '(' and ')'
insertions += 2;
}
}
}
i++;
}
// Add ')' for remaining unmatched '('
insertions += leftCount * 2;
return insertions;
}
C#:
public class Solution {
/// <summary>
/// Greedy approach with counter
/// Time: O(n) - single pass through string
/// Space: O(1) - constant extra space
/// </summary>
public int MinInsertions(string s) {
int insertions = 0;
int leftCount = 0;
int i = 0;
while (i < s.Length) {
if (s[i] == '(') {
leftCount++;
} else { // s[i] == ')'
if (i + 1 < s.Length && s[i + 1] == ')') {
// Found "))"
if (leftCount > 0) {
leftCount--;
} else {
// Need to add '('
insertions++;
}
i++; // Skip next ')'
} else {
// Found single ')'
if (leftCount > 0) {
leftCount--;
insertions++; // Need to add another ')'
} else {
// Need to add '(' and ')'
insertions += 2;
}
}
}
i++;
}
// Add ')' for remaining unmatched '('
insertions += leftCount * 2;
return insertions;
}
}
Key Insights
- Greedy Strategy: Process characters from left to right and make optimal choices
- Counter Approach: More space-efficient than stack approach
- Double Right Parentheses: Handle “))” as a unit
- Remaining Left Parentheses: Each unmatched ‘(’ needs two ‘)’
Edge Cases
- Empty String: Return 0
- All Left Parentheses: Need 2 * length insertions
- All Right Parentheses: Need length insertions
- Already Balanced: Return 0
Follow-up Questions
- Different Parentheses Types: Handle [], {}, () together
- Minimum Deletions: Find minimum deletions instead of insertions
- Wildcard Characters: Handle ‘*’ as wildcard
- Multiple Operations: Allow both insertions and deletions
Common Mistakes
- Not handling “))” as unit: Processing each ‘)’ separately
- Wrong counting: Incorrectly counting insertions needed
- Edge case handling: Not handling empty string or all same characters
- Stack vs counter: Using wrong approach for the problem