Count the Number of Bracket Reversals

In this problem, we will be given an expression of strings containing "(" and ")". The brackets may not be placed in a way that the expression is balanced. We have to reverse the brackets to make the expression balanced. At last, we have to return the number of times we reversed the brackets to make the expression balanced.

Examples:

From the above examples, we can conclude that an expression can be turned into a balanced expression only if the number of brackets is even; also, the number of both brackets, that is, "(" and ")" must be equal in numbers.

The basic approach to solve this problem will be to look at each bracket and count the number of times we reverse a bracket. We can do this recursively and keep track of the minimum number of counts required to make the expression balanced.

Time complexity: The time complexity to solve this problem using this approach will be O(2n).

Space Complexity: The space complexity to solve this problem using this approach will be O(n).

We can see that this approach is very inefficient.

An efficient solution can solve this problem in O(n) time. The idea of this approach is to remove all the balanced parts of the expressions in the first step. For instance, we will convert "}{{}}{{" to "}{{." When we take a closer look, we can notice that if we remove the balanced parts, we will always be left with a string of the form }}…}{{…{. The expression follows 0 or more closed brackets followed by 0 or more opened brackets.

Now we can easily calculate how many reversals we need to convert the expression into a balanced one. Let n be the number of closed brackets, and m be the number of open brackets. According to this, we will need [n / 2] + [m / 2] reversals. Hence we will need 2 reversals.

Below is the implementation of the above idea:

Code

Output:

The minimum number of reversals required are: 1

Time Complexity: O(n) will be the time complexity of this program.

Space Complexity: This program will take the O(n) space complexity.