Minimum number of bracket reversals to make an expression balanced

Intuition:

To find the minimum number of bracket reversals to make an expression balanced, firstly the number of balanced brackets must be found. Ignoring the balanced brackets, it will become easier to understand the required count.

Understanding:

Consider an example string: ")(())((("
Ignoring the already balanced brackets, the leftover part of the string will be: ")((("

Note: Once the balanced brackets are ignored, the string will always be left with some number of closing brackets followed by some number of opening brackets.

Say the number of open brackets are represented as open and number of closed brackets are represented as close, it can be seen that the minimum number of bracket reversals to make an expression balanced will depend upon:

The number of pairs that can be formed of open brackets or closed brackets. For every 2n open brackets, we only need to reverse n open brackets to form valid pairs.
Similarly for every 2n closed brackets, we only need to reverse n closed brackets to form valid pairs.
If there are any an odd number of open or closed brackets, then those will have to be reversed separately to form valid paranthesis.

Hence, the required minimum number of brackets will be:

      (open / 2) + (open % 2) + (close / 2) + (close % 2)

where open and close represent the number of invalid open and close brackets respectively.

Approach:

If the length of the string is odd, it's impossible to balance the parentheses, so return -1.
Initialize counters to track unbalanced opening and closing brackets.
Traverse the string:
- Increase the count for opening brackets.
- If a closing bracket is encountered, reduce the opening count if an opening bracket is available to form a balanced pair. Otherwise, increase the closing count for unmatched closing brackets.
After traversing the string, calculate the minimum number of reversals needed: Half of the remaining unbalanced opening and closing brackets need to be reversed.
Return the total count of reversals required to balance the string.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the minimum number of reversals required
    to convert the string into a balanced expression. */
    int countRev(string s) {
        int n = s.length(); // Size of string
        
        /* If string is of odd length, it is not 
        possible to balance the paranthesis */
        if(n % 2) return -1;
        
        // To store the count of opening and closing brackets
        int open = 0, close = 0;
        
        for(int i=0; i < n; i++) {
            // Increment open count if opening bracket is found
            if(s[i] == '(') open++;
            
            // Else (closing bracket is found)
            else {
                /* If a opening bracket is there, a pair
                of balanced paranthesis is formed */
                if(open > 0) open--;
                
                // Otherwise the closing bracket remain unbalanced
                else close++;
            }
        }
        
        // Computing the result
        int ans = (open / 2) + (open % 2) + (close / 2) + (close % 2)
        
        return ans; // Return the result
    }
};

int main(){
    string s =  ")(())(((";
    
    // Creating an instance of Solution class
    Solution sol; 
    
    /* Function call to find the minimum number of reversals 
    required to convert the string into a balanced expression. */
    int ans = sol.countRev(s);
    
    // Output
    cout << "The minimum number of reversals required are: " << ans << endl;
}
import java.util.*;

class Solution {
    /* Function to find the minimum number of reversals required
    to convert the string into a balanced expression. */
    public int countRev(String s) {
        int n = s.length(); // Size of string
        
        /* If string is of odd length, it is not 
        possible to balance the paranthesis */
        if(n % 2 != 0) return -1;
        
        // To store the count of opening and closing brackets
        int open = 0, close = 0;
        
        for(int i=0; i < n; i++) {
            // Increment open count if opening bracket is found
            if(s.charAt(i) == '(') open++;
            
            // Else (closing bracket is found)
            else {
                /* If a opening bracket is there, a pair
                of balanced paranthesis is formed */
                if(open > 0) open--;
                
                // Otherwise the closing bracket remain unbalanced
                else close++;
            }
        }
        
        // Computing the result
        int ans = (open / 2) + (open % 2) + (close / 2) + (close % 2);
        
        return ans; // Return the result
    }
}

class Main {
    public static void main(String[] args) {
        String s =  ")(())(((";
        
        // Creating an instance of Solution class
        Solution sol = new Solution(); 
        
        /* Function call to find the minimum number of reversals 
        required to convert the string into a balanced expression. */
        int ans = sol.countRev(s);
        
        // Output
        System.out.println("The minimum number of reversals required are: " + ans);
    }
}
class Solution:
    # Function to find the minimum number of reversals required
    # to convert the string into a balanced expression. 
    def countRev(self, s: str) -> int:
        n = len(s) # Size of string
        
        # If string is of odd length, it is not 
        # possible to balance the paranthesis 
        if n % 2 != 0:
            return -1
        
        # To store the count of opening and closing brackets
        open = 0
        close = 0
        
        for i in range(n):
            # Increment open count if opening bracket is found
            if s[i] == '(':
                open += 1
            
            # Else (closing bracket is found)
            else:
                # If a opening bracket is there, a pair
                # of balanced paranthesis is formed 
                if open > 0:
                    open -= 1
                
                # Otherwise the closing bracket remain unbalanced
                else:
                    close += 1
        
        # Computing the result
        ans = (open // 2) + (open % 2) + (close // 2) + (close % 2)
        
        return ans # Return the result

if __name__ == "__main__":
    s =  ")(())((("
    
    # Creating an instance of Solution class
    sol = Solution() 
    
    # Function call to find the minimum number of reversals 
    # required to convert the string into a balanced expression. 
    ans = sol.countRev(s)
    
    # Output
    print("The minimum number of reversals required are:", ans)
class Solution {
    /* Function to find the minimum number of reversals required
    to convert the string into a balanced expression. */
    countRev(s) {
        let n = s.length; // Size of string
        
        /* If string is of odd length, it is not 
        possible to balance the paranthesis */
        if (n % 2 !== 0) return -1;
        
        // To store the count of opening and closing brackets
        let open = 0, close = 0;
        
        for (let i = 0; i < n; i++) {
            // Increment open count if opening bracket is found
            if (s[i] === '(') open++;
            
            // Else (closing bracket is found)
            else {
                /* If a opening bracket is there, a pair
                of balanced paranthesis is formed */
                if (open > 0) open--;
                
                // Otherwise the closing bracket remain unbalanced
                else close++;
            }
        }
        
        // Computing the result
        let ans = Math.floor(open / 2) + (open % 2) + Math.floor(close / 2) + (close % 2);
        
        return ans; // Return the result
    }
}

const s =  ")(())(((";

// Creating an instance of Solution class
const sol = new Solution(); 

/* Function call to find the minimum number of reversals 
required to convert the string into a balanced expression. */
const ans = sol.countRev(s);

// Output
console.log("The minimum number of reversals required are:", ans);

Complexity Analysis:

Time Complexity: O(n) (where n is the length of the input string)
The input string is traversed once taking O(n) time.

Space Complexity: O(1)
Only a couple of variables are used taking constant space.

Problem List

Minimum number of bracket reversals to make an expression balanced

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Understanding:

Approach:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code