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

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

    # Add opening parentheses
    result += '(' * open_count

    # Append the original string
    result += s

    # Add closing parentheses
    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++;
                }
            }
        }

        // Add opening parentheses
        result.append("(".repeat(openCount));

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

        // Add closing parentheses
        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++;
            }
        }
    }

    // Add opening parentheses
    result += '('.repeat(openCount);

    // Append the original string
    result += s;

    // Add closing parentheses
    result += ')'.repeat(closeCount);

    return result;
}

// Test cases
console.log(balancedString("(()))"));  // Output: "(((())))"
console.log(balancedString("))()("));  // Output: "()()()()"