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 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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of