# Given a string of parentheses, find the balanced string that can be produced from it using the minimum number of insertions and deletions

By | January 25, 2024

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. For example, given “(()”, you could return “(())”. Given “))()(“, you could return “()()()()”.

To find the balanced string with the minimum number of insertions and deletions, you can follow these steps:

1. Count the number of opening and closing parentheses needed to make the string balanced.
2. Iterate through the string and keep track of the balance.
3. Add the necessary opening and closing parentheses to balance the string.

Python:

``````def balanced_string(s):
open_count = 0
close_count = 0
result = ""

# Count the number of opening and closing parentheses needed
for char in s:
if char == '(':
open_count += 1
elif char == ')':
if open_count > 0:
open_count -= 1
else:
close_count += 1

result += '(' * open_count

# Append the original string
result += s

result += ')' * close_count

return result

# Test cases
print(balanced_string("(()))"))  # Output: "(((())))"
print(balanced_string("))()("))  # Output: "()()()()"
``````

Java

``````public class BalancedString {

public static String balancedString(String s) {
int openCount = 0;
int closeCount = 0;
StringBuilder result = new StringBuilder();

// Count the number of opening and closing parentheses needed
for (char c : s.toCharArray()) {
if (c == '(') {
openCount++;
} else if (c == ')') {
if (openCount > 0) {
openCount--;
} else {
closeCount++;
}
}
}

result.append("(".repeat(openCount));

// Append the original string
result.append(s);

result.append(")".repeat(closeCount));

return result.toString();
}

public static void main(String[] args) {
System.out.println(balancedString("(()))"));  // Output: "(((())))"
System.out.println(balancedString("))()("));  // Output: "()()()()"
}
}``````

Java

``````function balancedString(s) {
let openCount = 0;
let closeCount = 0;
let result = "";

// Count the number of opening and closing parentheses needed
for (let char of s) {
if (char === '(') {
openCount++;
} else if (char === ')') {
if (openCount > 0) {
openCount--;
} else {
closeCount++;
}
}
}

result += '('.repeat(openCount);

// Append the original string
result += s;