# Find the minimum number of inversions needed to make the given expression balanced

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

For example,

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 –

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).

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 🙂