Find balanced string with minimum insertions and deletions

Problem

Given a string of parenthesis, if the parenthesis are not balanced, then return the balanced string than can be produced with the minimum number of insertions and deletions.

 Example

 Input: "(()"
 Output: "(())"

 Input: "))()("
 Output: "()()()()"

Approach

1. Read the problem statement “out loud” with attention to keywords. In this case focus on “minimum”, “insertions” and “deletions”.
2. Think about the expected output: is it possible to generate different strings? Ask the interviewer if it’s ok to generate “any” string as long as it’s balanced.
3. Is your algorithm different if you only use insertions? What if you only use deletions?
4. Write down all the edge cases: empty string, string with only 1 open parenthesis, string with only 1 closing parenthesis, etc.

Solution

This problem can be tackled with a greedy approach. The idea is to iterate over the string and keep a running counter of open parenthesis: increase the counter when you find an open parenthesis and decrease the counter when you find a closing parenthesis.

If the counter is 0 and you are visiting a closing parenthesis (which means the counter is in danger of becoming negative) then the string is unbalanced and you need to add an open parenthesis to counter balance the closing parenthesis.

Finally when you arrive at the end of the string and the counter is greater than 0 it means that we have visited more open parenthesis than closing parenthesis: append closing parenthesis until the counter becomes 0.

String fixParenthesis(String str) {

    // keep a running counter of open parenthesis
    int counter = 0;

    StringBuilder res = new StringBuilder();

    for(char c : str.toCharArray()) {

        if(c == '('){
            res.append('(');
            counter++;
        } else {
            if(counter == 0) {
                res.append('(');
            } else {
                counter--;
            }
            res.append(')');
        }
    }

    while(counter > 0) {
        res.append(')');
        counter--;
    }

    return res.toString();
}