Given an expression consisting of opening brace ‘{‘ and a closing brace ‘}’, find the minimum number of inversions needed to make the expression balanced.

Input: {{}{{}{{

Output: Minimum number of inversions needed is 2

{{}{{}{{ –> {{}{{}}{ –> {{}{{}}}

Input: {{{{{{

Output: Minimum number of inversions needed is 3

{{{{{{ –> {{{}{{ –> {{{}}{ –> {{{}}}

The idea is to traverse the given expression and maintain a count of open braces in the expression seen so far. If the current character is a opening brace ‘{‘, then we increment the count of opened braces by 1. If the current character is a closing brace ‘}’, then we check if it has any unclosed brace to its left (*look for non-zero opened brace count*). If any unclosed brace is found, we close it by using current brace and decrement the count of opened braces by one; else we convert the current closing brace ‘}’ to ‘{‘ and increment the total inversions needed and opening brace count by 1. After we are done processing each character in the expression, if there are n opened braces, we will need exactly n/2 inversion to close them.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <string> #include <climits> using namespace std; // Function to find the minimum number of inversions needed // to make the given expression balanced int findMinInversions(string exp, int n) { // if the expression has odd length, it cannot be balanced if (n & 1) { return INT_MAX; } int inversions = 0; // stores total inversions needed int open = 0; // stores total number of opening braces // traverse the expression for (int i = 0; i < n; i++) { // if current character is a opening brace if (exp[i] == '{') { open++; } // if current character is a closing brace else { // if a opening brace is found before, close it if (open) { open = open - 1; // decrement opening brace count } else // invert the closing brace i.e. change '}' to '{' { inversions++; // increment total inversions needed by 1 open = 1; // increment opening brace count } } } // for N opened brace, we need exactly N/2 inversions return inversions + open/2; } // main function int main() { string exp = "{{}{{}{{"; int n = exp.length(); int inv = findMinInversions(exp, n); if (inv != INT_MAX) cout << "Minimum number of inversions needed is " << inv; else cout << "Invalid input" << endl; return 0; } |

`Output:`

Minimum number of inversions needed is 2

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

A bit simpler version of the same