Strings: Get the minimum number of inversions needed to make an expression balanced

Problem Statement:

You are given a string consisting of “{” and “}”.
You need to find the minimum number of inversions needed to balance the expression.

Example

Input: "}{"
Output: 2

We need to change '}' to '{' and '{' to '}'.
Then the expression becomes balanced '{}'

Solution

The solution is very simple.

First step is to remove all the balanced brackets from the expression.

Example: “}{{}}{“, now remove “{{}}”, you are left with “}{” i.e unbalanced brackets.

If we have “m” number of closing brackets and “n” number of opening brackets.

The reversals required are ⌈m/2⌉ + ⌈n/2⌉.

The time complexity is O(n)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>

using namespace std;

int return_minimum_reversal(string expr) 
{ 
    int len = expr.length(); 
  
    // if the length is not even, then 
    // the expression is not balanced
    if (len%2) 
       return -1; 

    stack<char> s; 

    for (int i=0; i<len; i++) 
    { 
        if (expr[i]=='}' && !s.empty()) 
        { 
            if (s.top()=='{') 
                s.pop(); 
            else
                s.push(expr[i]); 
        } 
        else
            s.push(expr[i]); 
    } 
  

    int reduced_len = s.size(); 

    int n = 0; 
    while (!s.empty() && s.top() == '{') 
    { 
        s.pop(); 
        n++; 
    } 
  
    return (reduced_len/2 + n%2); 
} 
  
int main() 
{ 
   string expr = "}{"; 
   cout <<"The minimum reversal needed is "<< return_minimum_reversal(expr)<<endl; 
   return 0; 
} 

Output:

The minimum reversal needed is 2