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

1
2
3

Input: "(()"
Output: "(())"
Explanation: The balanced string can be obtained by adding one closing parenthesis.

Example 2

1
2
3

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:

  1. Traverse the string and use a counter to track the number of unmatched opening parentheses.
  2. For each closing parenthesis, check if there is an unmatched opening parenthesis that this can pair with.
  3. 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.
  4. If any unmatched opening parentheses remain, they require corresponding closing parentheses at the end of the string.

Approach

  1. Traverse the String: Use a counter to track unmatched opening and closing parentheses.
  2. 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.
  3. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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), where n 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.