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

(2 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂