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 –
 

Download   Run Code

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
foobar
Guest

A bit simpler version of the same