Problem
Given a string of parentheses, find the balanced string that can be produced from it using the minimum number of insertions and deletions. If there are multiple solutions, return any of them.
Examples
Example 1
Input: "(()"
Output: "(())"
Explanation: The balanced string can be obtained by adding one closing parenthesis.
Example 2
Input: "))()("
Output: "()()()()"
Explanation: The balanced string can be obtained by adding multiple opening and closing parentheses.
Solution
Method 1 - Using Counter
To balance the given string of parentheses, we need to count the unmatched opening and closing parentheses. Using this information, we can determine the minimum number of insertions and deletions required to produce a balanced string:
- Traverse the string and use a counter to track the number of unmatched opening parentheses.
- For each closing parenthesis, check if there is an unmatched opening parenthesis that this can pair with.
- If any unmatched closing parentheses remain after traversing the string, they must be handled by adding corresponding opening parentheses at the start of the string.
- If any unmatched opening parentheses remain, they require corresponding closing parentheses at the end of the string.
Approach
- Traverse the String: Use a counter to track unmatched opening and closing parentheses.
- Count Unmatched Parentheses:
- For each
(
, increment the unmatched opening count. - For each
)
, decrement the unmatched opening count if possible, otherwise increment the unmatched closing count.
- For each
- Construct Balanced String:
- Add unmatched closing parentheses at the beginning.
- Add the original string with unmatched closing parentheses removed.
- Add unmatched opening parentheses at the end.
Code
Java
public class Solution {
public String balanceParentheses(String s) {
int openCount = 0;
int closeCount = 0;
StringBuilder balanced = new StringBuilder();
// First pass to count unpaired parentheses and remove extra closing parentheses
for (char c : s.toCharArray()) {
if (c == '(') {
openCount++;
balanced.append(c);
} else if (c == ')') {
if (openCount > 0) {
openCount--;
balanced.append(c);
} else {
closeCount++;
}
}
}
// Construct the balanced string
StringBuilder result = new StringBuilder();
for (int i = 0; i < closeCount; i++) result.append(')');
result.append(balanced);
for (int i = 0; i < openCount; i++) result.append('(');
return result.toString();
}
}
Python
class Solution:
def balanceParentheses(self, s: str) -> str:
open_count = 0
close_count = 0
balanced = []
# First pass to count unpaired parentheses and remove extra closing parentheses
for char in s:
if char == '(':
open_count += 1
balanced.append(char)
elif char == ')':
if open_count > 0:
open_count -= 1
balanced.append(char)
else:
close_count += 1
# Construct the balanced string
balanced_string = ')' * close_count + ''.join(balanced) + '(' * open_count
return balanced_string
Complexity
- ⏰ Time complexity:
O(n)
, wheren
is the length of the input string, because we traverse the string once. - 🧺 Space complexity:
O(n)
, because the output string can be at most twice the length of the input string.