Find the minimum number of edits to balance parentheses?

Question

I was very confused about this question. I know about finding the edit distance between 2 strings using recursion and dynamic programming as an improvement, however am confused about how to go with this one.

Not sure if my thinking is correct. But we have a string of parenthesis which is unbalanced say

String s = "((())))";

How to find the String with balanced Parenthesis which requires minimum number of edits ?

Can some one explain this with an example ?

I am still not sure if I am explaining it correctly.

Answer 1

public static int minimumSwaps(String brackets) {
        if(brackets.length() % 2 !=0){
            return -1;
        }
        
        Map<Character, Character> bracketPairs = new HashMap<>();
        bracketPairs.put(')', '(');
        bracketPairs.put('}', '{');
        bracketPairs.put(']', '[');

        Stack<Character> stack = new Stack<>();
        int mismatches = 0;

        for (char ch : brackets.toCharArray()) {
            if (bracketPairs.containsValue(ch)) {
                // If it's an opening bracket
                stack.push(ch);
            } else if (bracketPairs.containsKey(ch)) {
                // If it's a closing bracket
                if (!stack.isEmpty() && stack.peek() == bracketPairs.get(ch)) {
                    stack.pop();
                }else {
                    mismatches++;
                }
            }
        }
       
        // The number of swaps needed is half the number of mismatches
        return (mismatches + stack.size()) / 2;
    }

Answer 2

 //fisher
   public int minInsertions(String s) {
        Stack<Character> stack = new Stack<>();
        int insertionsNeeded = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                if (stack.isEmpty()) {
                    stack.add(c);
                } else {
                    if (stack.peek() == ')') {
                        //in this case, we need to add one more ')' to get two consecutive right paren, then we could pop the one ')' and one '(' off the stack
                        insertionsNeeded++;
                        stack.pop();
                        stack.pop();
                        stack.add(c);
                    } else {
                        stack.add(c);
                    }
                }
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    //in this case, we need to add one '(' before we add this ')' onto this stack
                    insertionsNeeded++;
                    stack.add('(');
                    stack.add(c);
                } else {
                    if (stack.peek() == ')') {
                        //in this case, we could pop the one ')' and one '(' off the stack
                        stack.pop();
                        stack.pop();
                    } else {
                        stack.add(c);
                    }
                }
            }
        }
        if (stack.isEmpty()) {
            return insertionsNeeded;
        } else {
            while (!stack.isEmpty()) {
                char pop = stack.pop();
                if (pop == '(') {
                    insertionsNeeded += 2;
                } else {
                    insertionsNeeded++;
                    stack.pop();
                }
            }
            return insertionsNeeded;
        }
    }
}

Answer 3

I would use stack to balance them efficiently. Here is python code:

a=['(((((','a(b)c)','((())))',')()(()())))()((())((']


def balance(s):
  st=[]

  l=len(s)
  i=0

  while i<l:
    if s[i]=='(':
      st.append(i)
    elif s[i]==')':
      if st:
        st.pop()
      else:
        del s[i]
        i-=1
        l-=1

    i+=1

  while st:
    del s[st.pop()]

  return ''.join(s)

for i in a:
  print balance(list(i))

Output:

Empty 
a(b)c
((()))
()(()())()(())

Answer 4

The idea is simple:

Find final string having left over open and close brackets which couldn't make pair. Remember that in this final string, close brackets will be present 1st and then open brackets.

Now we will have to edit open brackets and close brackets separately.

eg: for close brackets:

     (1) if it is of even length:
              min edit to balance will be to change half close brackets to open brackets.
              So minEdit = closeBracketCount/2
.    (2) If it is of odd length:
             min edit to balance will be to do above step 1 and remove the remaining 1 bracket.
             So minEdit = closeBracketCount/2 + 1

For open brackets:
    (1) if it is of even length:
            min edit to balance will be to change half open brackets to close brackets.
            So minEdit = openBracketCount/2.
    (2) If it is of odd length:
           min edit to balance will be to do above step 1 and remove the remaining 1 bracket.
           So minEdit = openBracketCount/2 + 1

Here is the running code: http://codeshare.io/bX1Dt
Let me know your thoughts.

Upvotes: 3

Answer 5

I tired to solve the problem with DP algorithm and it passed a few test cases made up by myself. Let me know if you think it's correct.

Let P(i,j) be the minimum number of edits to make string S[i..j] balanced.

When S[i] equals S[j], the number of minimum edits is obviously P(i+1,j-1)

There are a few options to make the string balanced when S[i] != S[j], but in the end we could either add '(' to the front of i or ')' at the end of j, or remove the parenthesis at i or j. In all these cases, the minimum number of edits is min{P(i+1, j), P(i, j-1)} + 1.

We therefore have below DP formula:

P(i,j) = 0 if i > j
       = P(i + 1, j - 1) if S[i] matches S[j] OR S[i] and S[j] are not parenthesis
       = min{P(i + 1, j), P(i, j - 1)} + 1

Answer 6

Given a string consisting of left and right parentheses, we are asked to balance it by performing a minimal number of delete, insert, and replace operations.

To begin with, let's look at the input string and distinguish matched pairs from unmatched characters. We can mark all the characters belonging to matched pairs by executing the following algorithm:

1. Find an unmarked '(' that is followed by an unmarked ')', with zero or more marked characters between the two.
2. If there is no such pair of characters, terminate the algorithm.
3. Otherwise, mark the '(' and the ')'.
4. Return to step 1.

The marked pairs are already balanced at zero cost, so the optimal course of action is to do nothing further with them.

Now let's consider the unmarked characters. Notice that no unmarked '(' is followed by an unmarked ')', or else the pair would have been marked. Therefore, if we scan the unmarked characters from left to right, we will find zero or more ')' characters followed by zero or more '(' characters.

To balance the sequence of ')' characters, it is optimal to rewrite every other one to '(', starting with the first one and excluding the last one. If there is an odd number of ')' characters, it is optimal to delete the last one.

As for the sequence of '(' characters, it is optimal to rewrite every other one to ')', starting with the second one. If there is a leftover '(' character, we delete it. The following Python code implements the steps described above and displays the intermediate results.

def balance(s):  # s is a string of '(' and ')' characters in any order
  n = len(s)
  print('original string: %s' % s)

  # Mark all matched pairs
  marked = n * [ False ]
  left_parentheses = []
  for i, ch in enumerate(s):
    if ch == '(':
      left_parentheses.append(i)
    else:
      if len(left_parentheses) != 0:
        marked[i] = True
        marked[left_parentheses.pop()] = True

  # Display the matched pairs and unmatched characters.
  matched, remaining = [], []
  for i, ch in enumerate(s):
    if marked[i]:
      matched.append(ch)
      remaining.append(' ')
    else:
      matched.append(' ')
      remaining.append(ch)
  print('  matched pairs: %s' % ''.join(matched))
  print('      unmatched: %s' % ''.join(remaining))

  cost = 0
  deleted = n * [ False ]
  new_chars = list(s)

  # Balance the unmatched ')' characters.
  right_count, last_right = 0, -1
  for i, ch in enumerate(s):
    if not marked[i] and ch == ')':
      right_count += 1
      if right_count % 2 == 1:
        new_chars[i] = '('
        cost += 1
        last_right = i
  if right_count % 2 == 1:      # Delete the last ')' if we couldn't match it.
    deleted[last_right] = True  # The cost was incremented during replacement.

  # Balance the unmatched '(' characters.
  left_count, last_left = 0, -1
  for i, ch in enumerate(s):
    if not marked[i] and ch == '(':
      left_count += 1
      if left_count % 2 == 0:
        new_chars[i] = ')'
        cost += 1
      else:
        last_left = i
  if left_count % 2 == 1:      # Delete the last '(' if we couldn't match it.
    deleted[last_left] = True  # This character wasn't replaced, so we must
    cost += 1                  # increment the cost now.

  # Display the outcome of replacing and deleting.
  balanced = []
  for i, ch in enumerate(new_chars):
    if marked[i] or deleted[i]:
      balanced.append(' ')
    else:
      balanced.append(ch)
  print('        balance: %s' % ''.join(balanced))

  # Display the cost of balancing and the overall balanced string.
  print('           cost: %d' % cost)
  result = []
  for i, ch in enumerate(new_chars):
    if not deleted[i]:  # Skip deleted characters.
      result.append(ch)
  print('     new string: %s' % ''.join(result))


balance(')()(()())))()((())((')

For the test case ')()(()())))()((())((', the output is as follows.

original string: )()(()())))()((())((
  matched pairs:  ()(()())  () (())
      unmatched: )        ))  (    ((
        balance: (        )   (    )
           cost: 4
     new string: (()(()()))()((()))

Answer 7

While this interesting problem can be solved with dynamic programming as mentioned in the comments, there exists an easier solution to it. You can solve it with the greedy algorithm.

Idea for this greedy algorithm comes from how we check the validity of parentheses expression. You set counter to 0 and traverse the parentheses string, add 1 at "(" and substract 1 at ")". If counter always stays above or at 0 and finishes at 0, you have a valid string.

This implies that if the lowest value that we encountered while traversing is -maxi, we need to add exactly -maxi "(" at the start. Adjust final counter value for added "(" and add enough ")" at the end to finish at 0.

Here is the pseudo-code for the algorithm:

counter = 0
mini = 0
for each p in string:
  if p == "(":
    counter++
  else:
    counter--

  mini = min(counter, mini)

add -mini "(" at the start of the string
counter -= mini
add counter ")" at the end of the string